tony9402

알고리즘 분류 : 다이나믹 프로그래밍(DP) 문제 : 1, 2, 3 더하기 이 문제는 계산을 어떻게 할껀지 점화식을 세우면 금방 푸는 문제이다. 난 이 문제를 풀면서 재귀적인 풀이를 생각하며 풀었다. 5라는 숫자가 있을 때, 여기서 1, 2, 3을 뺀 숫자들 4, 3, 2가 1, 2, 3의 합으로 나타내는 경우의 수를 다 더하면 된다는 것을 발견하였다. 이를 수식으로 쓰면 DP[n] = DP[n-1] + DP[n-2] + DP[n-3]이다. 여기서 n을 1, 2, 3을 빼다 보면 DP[0]인 경우가 나온다. 이럴 때, DP[0]의 값을 뭐로 하면 좋을까? 간단한 예를 보자. 2라는 숫자가 있다. 2라는 숫자는 보자마자 1 + 1와 2로 경우의 수가 나온다. 이를 내가 푼 방식으로 한번 보자. 2는 1, ..