[백준 알고리즘/Python] 9095 1,2,3더하기

문제

 

문제이해

1 => 1                           )=>1개

2 => 1+1, 2                    )=>2개

3 => 1+1+1 , 1+2, 2+1, 3  )=>4개

 

만약 4를 1,2,3으로만 표현하려면 1+3, 2+2이 됩니다. 즉 1로 나타내는수, 2로 나태는수, 3으로 나태내는수를 모두 더하면 됩니다.

1로 나타내는수, 2로 나태는수, 3으로 나태내는수

1               +         2        +         4           =7개로 이 됩니다.

 

dp[1]	1		1개
dp[2]	2		2개
	1+1
dp[3]	3		4개
	1+2 2+1 1+1+1	dp[2]에 1 더해주기
dp[4]	1+3 3+1 1+2+1 2+1+1 1+1+1+1	dp[3]에 1 더해주기	7개
	2+2 1+1+2	dp[2]에 2 더해주기
dp[5]	1+3+1 3+1+1 1+2+1+1 2+1+1+1 1+1+1+1+1 2+2+1 1+1+2	dp[4]에 1 더해주기	13개
	3+2 1+2+2 2+1+2 1+1+1+2	dp[3]에 2 더해주기
	2+3 1+1+3	dp[2]에 3 더해주기

만약 5를 1,2,3으로만 표현하려면

4로 표현하는 것들의 +1

3으로 표현하는 것들의 +2

2로 표현하는 것들의 +3 을 하면 됩니다.