문제는 다음과 같다.
처음 문제를 보고 어찌 접근해야 하나 고민이었다. 위에 문제 처럼 먼저 4를 분해해 보면 이렇다.
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2
1 + 3
3 + 1
뭔가 규칙성이 보이지 않는가?
이번엔 10으로 다시 한번 해보자.
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2
1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 1
1 + 1 + 1 + 1 + 1 + 1 + 2 + 1 + 1
1 + 1 + 1 + 1 + 1 + 2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2 + 1 + 1 + 1 + 1 + 1
1 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1
1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1 + 3
.
.
.
10으로 봤을때 표현할 수 있는 방법의 수가 하나씩 줄어드는것이 보인다.
4를 기준으로 처음(1+1+1+1)부터 끝부분 까지 하나가 합쳐질 때마다 표현할 수 있는 가짓수가 하나씩 줄어든다. 이를 토대로 식을 만들어 보면
(i-1) + (i-2) + (i-3)이고 자세히 풀어 쓰자면
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
이다.
변수명 dp는 dynamic programming 파트라 그냥 줄여서 dp라 명했다.
아래는 정답코드다.
T = int(input()) # 몇번 반복할꺼야?
dp = [0]*(1001) # 길이는 임시로 만들었다.
dp[0] = 1 # 초깃값 지정하기
for i in range(T): # 3회 반복하는데
n = int(input()) # 반복할때마다 값을 넣어라.
for i in range(1,n+1): # 첫번째 부터 n+1까지 아래를 반복해라.
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
print(dp[n])
