15988번: 1, 2, 3 더하기 3 www.acmicpc.net 이 문제는 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다. 이때 정수를 1, 2, 3의 합으로 표현할 때 1, 2, 3의 개수가 같고 더하는 순서만 다른 방법는 다른 방법로 간주한다. 특히 뒤의 조건 때문에 이 문제는 쉽게 해결할 수 있다. 우선 각 정수 n를 1, 2, 3의 합으로 나타내는 방법의 수를 n번째 인덱스에 저장하는 배열을 dp라고 하자. 그러면 dp[1] = 1, dp[2] = 2, dp[3] = 4를 만족한다. 왜냐하면 1은 1로 표현 가능하고, 2는 2, 1+1로 표현 가능하며, 3은 1+1+1, 1+2, 2+1, 3으로 표현 가능하기 때문이다. 만약 n이 4 이상인 경우, n은 (n-1)+1, (..