산 넘어 산 개발일지

풀이 키워드 DP 숫자들을 사용해 나가는 DP 문제는 대부분 이전 숫자들을 이용하는 것이 많다. 즉 dp[i]를 구하기 위해서는 dp[i-1] 이나 dp[i-2] 등을 이용하는 것이다. 이번 문제도 크게 다르지 않았다. 먼저, 이번 문제의 특별한 숫자들로는 1, 2, 3이 있다. 이 숫자들을 사용해 앞으로의 숫자들에 대한 덧셈 식을 구현하는 것이다. 따라서, 먼저 이 숫자들이 몇 개의 덧셈식을 가지고 있는지를 계산해놓자. dp[1] = 1 (1) dp[2] = 2 (1+1, 2) dp[3] = 4 (1+1+1, 1+2, 2+1, 3) 이제 4를 보자. 4는 문제에 나와있듯이 7개의 덧셈식이 존재한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 이를 맨 뒤 숫자만 제외하고, 될 수..