1,2,3 더하기 5 (15990)

1,2,3 더하기 5 (15990)

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 15990 1,2,3 더하기 5
const long long MOD = 1000000009;
int n;
// cache[i][j] : 정수 i 의 합을 j 로 끝나는 방법의 수 를 저장
long long cache[100000][4];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	int t;
	
	cin >> t;
	
	cache[1][1] = 1;
	cache[2][2] = 1;
	cache[3][1] = 1;
	cache[3][2] = 1;
	cache[3][3] = 1;
	
	for(int i = 4; i <= 100000; i++){
		cache[i][1] = (cache[i - 1][2] + cache[i - 1][3]);
		cache[i][2] = (cache[i - 2][1] + cache[i - 2][3]);
		cache[i][3] = (cache[i - 3][2] + cache[i - 3][1]);

		cache[i][1] %= MOD;
		cache[i][2] %= MOD;
		cache[i][3] %= MOD;
	}
	
	while(t--){
		cin >> n;
		
		cout << (cache[n][1] + cache[n][2] + cache[n][3]) % MOD << '\n';
		
	}
	
	
}

 

해설

---

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

1

풀이

1. 기존의 1,2,3 더하기 문제와 같았다.

- 마지막으로 끝나는 수가 1 또는 2 또는 3 이다. 하지만, 그 바로 이전의 수를 알아야 하므로, 기존의 점화식은 쓸 수 없었다. 새로운 조건을 넣어 점화식을 만들어보자.

2. cache[i][j] : 정수 i 의 합이, j 로 끝나는 방법의 수 를 저장 하였다. 

- 이렇게 된다면

 

cache[i][j] = cache[i - j][ (j + 1) % 3 ] + cache[i - j][ (j + 2) % 3]

 

이라는 점화식을 도출해낼 수 있다.

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

1. 너무 잦은 MOD.

- 너무 잦은 MOD 는 시간 초과를 야기하는 원인이 될 수 있다.

2. 테스트 케이스를 고려한 문제풀이가 필요했다.

- N의 최대 크기는 100,000 이다. 처음 문제에 접근했을 때는 이런 방식이었다.

1. 테스트 케이스의 크기를 받는다.

2. 각 케이스 마다 1 부터 케이스 n 까지의 반복문을 돌려 답을 도출한다.

다음에 생각해낸 방법. 시간을 많이 단축시킨 방법은 이러하다.

1. 1 부터 n 의 최대 크기 까지 반복문을 돌려 모든 답을 도출한다.

2. 테스트 케이스의 크기와 케이스를 받는다.

3. 답을 출력한다.

아래의 방법이 매우 효과적이었다. 잘 고려해보자.