[백준] 1563번 - 개근상 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법(Dynamic Programming) - 개근상

-> https://www.acmicpc.net/problem/1563

1563번: 개근상

 

cache[ i ][ j ][ k ]를 길이가 i이고 지각(L)이 j번이면서 끝문자의 연속 결석 회수가 k번으로 정의한다. 가령, 'LOAA'는 cache[4][1][2]의 한 요소이고, 'OALAO'는 cache[5][1][0]의 한 요소이다. 결석은 세번 연속으로 하지 않는 이상 개근상에 영향을 주지 않기 때문에 끝에 연속된 개수만 세어주면된다.

 

 

 

C++ 소스코드)

 

	#include <bits/stdc++.h>
	#define endl "\n"
	#define ll long long
	#define INF 987654321
	#define MAX 52
	#define MOD 1000000
	using namespace std;
	typedef pair<int, int> p;
	int cache[1001][2][3];
	int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	cache[1][0][0] = 1;
	cache[1][1][0] = 1;
	cache[1][0][1] = 1;
	for (int i = 2; i <= n; ++i) {
	cache[i][0][0] = (cache[i - 1][0][0] % MOD + cache[i - 1][0][1] % MOD + cache[i - 1][0][2] % MOD) % MOD;
	cache[i][0][1] = cache[i - 1][0][0] % MOD;
	cache[i][0][2] = cache[i - 1][0][1] % MOD;
	cache[i][1][0] = (cache[i - 1][0][0] % MOD + cache[i - 1][0][1] % MOD + cache[i - 1][0][2] % MOD + cache[i - 1][1][0] % MOD + cache[i - 1][1][1] % MOD + cache[i - 1][1][2] % MOD) % MOD;
	cache[i][1][1] = cache[i - 1][1][0] % MOD;
	cache[i][1][2] = cache[i - 1][1][1] % MOD;
	}
	int res = 0;
	for (int j = 0; j < 3; ++j)
	for (int k = 0; k < 2; ++k)
	res += cache[n][k][j];
	cout << res % MOD << endl;
	return 0;
	}

view raw 1563.cpp hosted with ❤ by GitHub

 

PS. Top-down으로 풀려다 시간 지체됐다...