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

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

입출력 예

입출력 예 설명

해결

점화식이 보인다면 동적 프로그래밍으로 해결할 수 있다. 1 -> 1 , 2 -> 2 , 3 -> 4, 4 -> 7, 5 -> 12 ... 

d[n] = d[n-1] + d[n-2] + d[n-3] 을 찾을 수 있다.

 

코드

 

느낀점

5를 직접 찾아보니까 15가 나와버려서 점화식을 찾는데 실패했다... 그래서 다른 블로그를 참고해서 풀었다. 그리고 런타임 에러가 떠서 배열의 크기를 1000으로 고정해서 풀었다. 입력 제한이 좁은 경우 고정해서 푸는게 효율적이다.

 

출처

https://zorba91.tistory.com/43

[java] 백준 알고리즘 9095번 1,2,3 더하기 풀이 소스