문제
정수 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부터 5까지의 경우를 모두 적은 것이다. 이전의 경우들을 보며 연관성이 있을 것이라는 의심을 시작해야한다.
5를 만들기 위해서는
4가 만들어지는 모든 경우에 1이 더해진 경우
3이 만들어지는 모든 경우에 2가 더해진 경우
2가 만들어지는 모든 경우에 3이 더해진 경우
의 합이 5에 대한 경우의 수이다.
해당 문제는 1,2,3만을 이용하도록 조건이 주어진 문제이지만 만약 4도 이용할 수 있도록 주어진다면
4가 만들어지는 모든 경우에 1이 더해진 경우
3이 만들어지는 모든 경우에 2가 더해진 경우
2가 만들어지는 모든 경우에 3이 더해진 경우
1이 만들어지는 모든 경우에 4가 더해진 경우
이렇게 경우의 수가 추가될 것이다. 이 안에서의 규칙성도 보이지 않는가? 이것을 잊지 말자.
연관 : DP
조금만 더