[dp] 15988 1,2,3 더하기 3

15988 1,2,3 더하기 3

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 15988 1,2,3 더하기 3
const long long MOD = 1000000009;
const int MAX = 1000000;
int n;
int cache[MAX + 1];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	int t;
	
	cin >> t;
	
	cache[1] = 1;
	cache[2] = 2;
	cache[3] = 4;
	
	for(int i = 4; i <= MAX; i++){
		cache[i] = (cache[i - 1] + cache[i - 2]) % MOD + cache[i - 3];
		cache[i] %= MOD;
	}
	
	while(t--){
		cin >> n;
		
		cout << cache[n] << '\n';
		
	}
	
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

1. 브루트 포스가 안된다는 것은, N 의 범위로 이미 깨달을 수 있다.

2. 어떤 수 n 은

(n - 1) + 1

(n - 2) + 2

(n - 3) + 3

으로 나타낼 수 있다.

3. cache[i] : A[i] 를 1,2,3 의 합으로 나타내는 방법의 수 라 정의한다.

4. 그러므로, cache[i] = cache[i - 1]  + cache[i - 2] + cache[i - 3] 이다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1. 항상 중요한 것은 끝에 무엇이 오느냐 이다.

2. int 와 long long 형의 차이를 더 주의깊게 생각했어야 했다. 처음에 잘 생각하지 않아 틀린 답을 내놓았었다. 10억 3개를 더하면 30억 으로, int 형을 초과할 수 있으니 3개를 더하는 과정 중, 한번의 MOD 연산을 거쳐야 올바른 답을 내놓는다. 그렇지 않으면 , 오버플로우가 발생해 틀린 답을 내놓는다.