[BOJ] 15988번 : 1,2,3 더하기 3

1. problem : 

https://www.acmicpc.net/problem/15988

 

 

2. solution 1:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int val = 1000000009;
int n; 
ll d[1000005]; 
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	d[0] = 1, d[1] = 1, d[2] = 2;
	for (int i = 3; i <= 1000000; i++) {
		d[i] = (d[i - 1] + d[i-2] + d[i-3]) % val;
	}
	cin >> n; 
	while (n--) {
		int x; 
		cin >> x; 
		cout << d[x] << '\n';
	}

}

dp를 이용해 풀었다. 따라서, 세 가지 스텝을 따른다. 

첫 번째, 테이블을 정의한다. d [i] = i일 때 경우의 수 

두 번째, 점화식을 작성한다. di] = d [i-1] + d [i-2] + d [i-3] 

세 번째, 초기값을 설정한다. d [0] = 1, d [1] = 1, d [2] = 2

 

3. solution 2 :

// Authored by : Hot6Mania
// Co-authored by : -
// http://boj.kr/945b646aaf504415a5efd80a21dff6b7
#include <bits/stdc++.h>
using namespace std;

int n;
int d[1000010];
int mod = 1e9 + 9;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  d[1] = 1; d[2] = 2; d[3] = 4;
  for(int i = 4; i <= 1000000; ++i)
    for(int j = 1; j <= 3; ++j)
      d[i] = (d[i] + d[i-j]) % mod;
  
  int t;
  cin >> t;
  while(t--){
    cin >> n;
    cout << d[n] << '\n';
  }
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/15988.cpp

basic-algo-lecture/0x10/solutions/15988.cpp at master · encrypted-def/basic-algo-lecture

모듈러 연산을 사용했다. 내 코드는 따지고 보면, 오류가 날 수 있었다. 다음에는 나도 이렇게 코드를 작성하도록 해야겠다. 

 

★ 모듈러 연산 : ( a + b ) % m == ((a % m) + (b % m)) % m