https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 필요한 배경지식 다이나믹 프로그래밍 문제 해결 방법 동전의 순서는 중요하지 않으므로 동전별로 차례대로 K원을 몇개나 만들 수 있는지 다이나믹 프로그래밍 하면 된다. 문제에서 주어진 입력으로 예를 들어보겠다. dp[K]를 'K원으로 만들 수 있는 동전조합의 수' 라고 할때 먼저 base case로 dp[0] = 1 을 정의할 수 있다. ('0원을 만들 수 있는 경우는 한가지'라고 인..
https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 필요한 배경지식 다이나믹 프로그래밍 문제 해결 방법 3차원 배열을 사용하여 DP로 문제를 해결했습니다. [1,4] 범위의 수가 N만큼 주워질때 배열 dp[n][x][y] = k에 대한 의미는 다음과 같습니다. n의 범위: [0,N] x, y의 범위: [0,4] k: n번째 수까지 입력 받았을때, 두 발의 위치가 x, y인 경우에 사용된 최소의 힘 위와 같이 정의한..
www.acmicpc.net/problem/2031 2031번: 이 쿠키 달지 않아! 첫 번째 줄에 4개의 자연수 T, N, D, K가 주어집니다. (1 ≤ T ≤ 109, 1 ≤ N ≤ 106, 1 ≤ D ≤ 109, 1 ≤ K ≤ 10) 두 번째 줄에 N 종류의 음식 각각을 먹을 시각을 나타내는 N 개의 자연수 a1, ..., aN이 주어집 www.acmicpc.net 재미있는 DP문제였습니다. 다이어트 효과가 최대가 되려면 다이어트가 효과가 유지되는 시간안에 음식이 가장 많이 포함되어 있어야 합니다. 우선 단순하게 K=1일때의 문제를 생각해 봅시다. 위에서 정의한 문제를 'D만큼의 범위안에 포함할 수 있는 원소의 최대 개수'로 치환할 수 있습니다. 그렇다면 이 문제는 정렬과 이분탐색을 이용하면 O(..