반응형
문제 링크 : 백준 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
- 예시
- 입력 : 3 4 7 10
- 출력 : 7 44 274
풀이
직접 다 일일이 손으로 써가면서 만들어봐야 함. 그래서 규칙을 찾고 점화식으로 만들어서 풀면 됨. 내가 찾은 점화식은 f(n) = f(n-1) + f(n-2) + f(n-3) 이었음.
코드
#include <iostream>
#include <algorithm>
using namespace std;
int cache[11];
int main() {
int T, n;
cin >> T;
cache[1] = 1;
cache[2] = 2;
cache[3] = 4;
cache[4] = 7;
for(int t = 0; t < T; t++) {
cin >> n;
for(int i = 5; i <= n; i++) {
cache[i] = cache[i-1] + cache[i-2] + cache[i-3];
}
cout << cache[n] << endl;
}
return 0;
}
반응형
'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글
[프로그래머스] 완주하지 못한 선수 Python (0) | 2020.03.16 |
---|---|
[백준 10844] 쉬운 계단 수 C++ (0) | 2020.01.19 |
[백준 11727] 2xn 타일링 2 c++ (0) | 2020.01.14 |
[백준 11726] 2xn 타일링 c++ (0) | 2020.01.08 |
[백준 1463] 1로 만들기 C++ (0) | 2020.01.05 |