DP

[백준] 15988번 1, 2, 3 더하기 3

문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 해당 문제의 예시 입/출력을 보자. 4, 7, 10과 같은 작은 수가 나오더라도 이에 수 십배의 경우의 수가 나온다. n의 최댓값이 1,000,000인 것을 감안하면 완전 탐색은 불가능하다. 문제를 조금 더 분석해보자. 식으로 나타낼 수 있는 숫자는 1, 2, 3이다. 나타내야 하는 수를 k라 할 때, k를 나타내기 위해서는 k보다 작은 수에서 1,2,3을 더하면 된다. 즉 k를 1,2,3으로 나타 낼 수 있는 방법 k-1 +1, ..

동적계획법(Dynamic Programming)

동적 계획법이란? 하나의 문제는 단 한 번만 풀도록 하는 알고리즘입니다. 일반적으로 상당수 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있습니다. 단순 분할 정복으로 풀게 되면 심각한 비효율성을 낳는 대표적인 예시로는 피보나치 수열이 있습니다. 동적 계획법을 사용할 수 있는 조건 Problem가 더 작은 sub-problem으로 쪼개질 경우 이 작은 sub-problem의 solution으로 큰 problem의 solution을 구할 수 있을 경우 sub-problem이 겹칠 경우 피보나치 수열 위 공식에서 Fn은 Fn-1과 Fn-2로 쪼개지면서 조건 1을 만족시킨다. 그리고 fn-1과 fn-2로 fn의 값을 구할 수 있으므로 조건 2를 만족시킨다. 마지막으로 중복의 fn을 가지므로 조건 ..