백준) 코딩테스트 2022, 12, 29

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

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <string>
#include <string.h>
#include <math.h>
#include <queue>

#define MOD 1000000009

using namespace std;

long long dp[100001][4];

int main()
{
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(NULL);

// 1, 2, 3만 가지고 합을 나태내야 한다.
// 연속적으로 같은 숫자는 사용 불가능
// 무조건 1개의 숫자는 사용해야한다.

// 1, 2, 3이 바로 전 수에서 사용이 되었나를 찾아야한다. ex) 3 -> 숫자1, 2, 3 = 1, 1, 1 / 4 -> 숫자1, 2, 3 = 2, 0, 1
// 그 3이 어떤 수의 합인지는 모르겠으나 무조건 3이 더해져야 4가 생성되며, 하나씩 체크를 해야한다.
// 만약 4를 표현하는데 있어 맨뒤에 마지막 더해야 하는 수가 1이라고 가정하면 앞에 합은 무조건 3이 나와야한다
// 1이라면 3을 표현했던 경우에 수를 뽑아낸 곳을 찾아가서 1을 뺀 2, 3이 더해져서 3이 된 경우의 수 합을 1의 숫자 자리에 가져온다
// 이를 2일떄랑 3일때를 반복하면 각 자리에 그전에 있던 경우에 수들의 합이 합처져서 4의 경우 3가지의 경우의 수가 나온다.
// 뒤를 판단하는 이유는 중복된 수가 연달아 나오는지 확인하기 위해


// dp[i][j] : i는 index j는 1, 2, 3을 가지고 합을 나타내기 위한 자리
dp[1][1] = dp[2][2] = 1;
dp[3][1] = dp[3][2] = dp[3][3] = 1;

for (int i = 4; i <= 100000; i++)
{
// 순서대로 뒤가 1이라면 2라면 3이라면 dp의 값을 담아놓는다.
dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD;
dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD;
}

int t;
long long n;
cin >> t;

while (t--)
{
cin >> n;

// i가 저장된 수를 n을 통해서 값을 출력
cout << (dp[n][1] + dp[n][2] + dp[n][3]) % MOD << '\n';
}

return 0;
}

 

아직도 알고리즘 관련한 문제들은 접근은 가능하나 코드를 작성함에 있어 많은 문제들이 생긴다. DP문제를 골랐지만 전에 풀었던 1, 2, 3 더하기 문제와는 난이도가 달랐다. 규칙을 찾는데 막혀서 결국 구글링을 통해 답을 보고 생각했으나 한시간 정도가 걸릴만큼 이해력에 있어 많이 부족하다. 이렇게 식을 짜내여 나가는 연습도 이제부터 해야겠다