취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5546번 문제인 파스타이다.
문제는 아래 링크를 확인하자.

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

i일까지 파스타를 먹었을 때 가능한 상태는 다음의 여섯가지이다:

1~3. 이틀 연속 토마토 소스/크림 소스/바질 소스 파스타를 먹은 상태

4~6. 어제와 다르게 오늘은 토마토 소스/크림 소스/바질 소스 파스타를 먹은 상태

각 날의 위 여섯가지 상태의 경우의 수를 점화식으로 잘 관리해나가면 문제를 쉽게 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int plan[101];
int A[101]; // 토마토
int AA[101]; // 토마토토마토
int B[101]; // 크림
int BB[101]; // 크림크림
int C[101]; // 바질
int CC[101]; // 바질바질

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

	int N, K; cin >> N >> K;
	while (K--) {
		int x, y; cin >> x >> y;
		plan[x] = y;
	}

	if (plan[1] == 1) A[1] = 1;
	else if (plan[1] == 2) B[1] = 1;
	else if (plan[1] == 3) C[1] = 1;
	else A[1] = B[1] = C[1] = 1;

	for (int i = 2; i <= N; i++) {
		if (plan[i] == 1) {
			A[i] = (B[i - 1] + BB[i - 1] + C[i - 1] + CC[i - 1]) % 10000;
			AA[i] = A[i - 1];
		}
		else if (plan[i] == 2) {
			B[i] = (A[i - 1] + AA[i - 1] + C[i - 1] + CC[i - 1]) % 10000;
			BB[i] = B[i - 1];
		}
		else if (plan[i] == 3) {
			C[i] = (A[i - 1] + AA[i - 1] + B[i - 1] + BB[i - 1]) % 10000;
			CC[i] = C[i - 1];
		}
		else {
			A[i] = (B[i - 1] + BB[i - 1] + C[i - 1] + CC[i - 1]) % 10000;
			AA[i] = A[i - 1];
			B[i] = (A[i - 1] + AA[i - 1] + C[i - 1] + CC[i - 1]) % 10000;
			BB[i] = B[i - 1];
			C[i] = (A[i - 1] + AA[i - 1] + B[i - 1] + BB[i - 1]) % 10000;
			CC[i] = C[i - 1];
		}
	}

	cout << (A[N] + AA[N] + B[N] + BB[N] + C[N] + CC[N]) % 10000;
}