정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. www.acmicpc.net 1. 풀이 문제에 있는 예시는 M이 너무 크므로, 다음과 같은 예시를 들어보자. 동전 종류 : 2, 4, 5 만들어야 하는 금액 : 10 기본 개념은, 첫 번째 ~ i 번째 까지의 동전을 사용했을 때,..

0. 문제 주소 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 풀이 문제에서 예시로 준 input을 사용하자. input :: ACAYKP CAPCAK 표로 이해하면 편하다. 다음과 같이 2차원 dp 배열을 설계한다. 0 1 2 3 4 5 6 C A P C A K 0 0 0 0 0 0 0 0 1 A 0 2 C 0 3 A 0 4 Y 0 5 K 0 6 P 0 ACAYKP를 str1, CAPCAK를..

0. 문제 주소 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 1. 풀이 이게 왜 골드 1이지??? 기존 문제들과 달랐던 점은 다음과 같다. 지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. dp 배열은 3차원으로 짰는데, dp[i][j][0] = (i, j) 기준 위쪽, 왼쪽에서 (i, j)로 올 때 가장 큰 값을 저장 dp[i][j][1] = (i, j)..