백준 9095번 1,2,3 더하기

정답 :

TMI : 비슷한 문제를 코테에서 봤었는데, 이렇게 푸는 것이였구나...

4를 예로 들었을 때, 방법의 수는 총 7가지였다.

 

1+1+1+1 , 1+2+1, 2+1+1,3+1 => (3을 1,2,3의 합으로 표현한 것) + 1 => Array[3]

1+1+2,2+2 => (2를 1,2,3의 합으로 표현한 것) + 2 => Array[2]

1+3 => (1을 1,2,3의 합으로 표현한 것) + 3 => Array[1]

 

따라서 Array[4] = Array[1] + Array[2] + Array[3] 이 된다.

 

대단하다..