[백준] 5546번: 파스타

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

5546번: 파스타

---

이전 기록을 토대로 현재 경우의 수를 갱신하는 dp 문제다.

 

1. 문제 조건

1) 1 ~ N 일 동안 파스타를 먹을 수 있는 방법의 가짓수를 출력한다.

2) 파스타는 토마토, 크림, 바질이 있다.

3) 3일 연속 같은 파스타를 먹을 수 없다.

4) N일 중 K일에는 그 날 먹을 파스타가 정해져 있다.

 

2. dp 배열 정의

3일 연속 같은 파스타를 먹지 못하니까,

처음에는 전 날과 전전 날에 먹은 파스타를 기록하려고 했다.

그러다보니 날짜와 현재 파스타까지 고려해야해서 4차원 dp 배열을 사용해야 했다.

 

이건 좀 아니다 싶어서 생각을 해보니,

그냥 연속으로 같은 파스타를 먹었는지 여부만 판단하면 될 것 같았다.

즉, 전 날에 전전 날과 다른 파스타를 먹었다면, 전 날에 먹은 파스타만 기억하면 된다.

 

전 날과 전전 날에 먹은 파스타의 종류에 따라 2차원 dp 배열을 정의하기로 한다.

#define MAXN 101
#define MAXK 101

#define NOT 0	// 먹을 파스타를 정하지 않음
#define T   1	// 전 날에 토마토
#define C   2	// 전 날에 크림
#define B   3	// 전 날에 바질
#define TT  4	// 전 날과 전전 날에 토마토
#define CC  5	// 전 날과 전전 날에 크림
#define BB  6	// 전 날과 전전 날에 바질

#define MAXP 7	// 파스타 조합의 개수

// dp[n][p] = n일차에 p조합으로 먹었을 때의 경우의 수
int dp[MAXN][MAXP];

// pasta[k] = k일에 먹을 파스타의 종류 (1, 2, 3)
int pasta[MAXK];

 

3. 해결법

k일에 먹을 파스타는 pasta[k] 에 저장해서 사용하기로 한다.

 

1) n = 1 (base)

- 1일차에 먹을 파스타가 미리 정해질 수도 있다.

- 따라서 pasta[1] = NOT 인지 여부를 확인해서 dp[1][?] 값을 초기화한다.

- 정해져 있다면 그 파스타만 1로, 아니라면 모든 파스타를 1로 한다. 물론 T, C, B 만 초기화해야 한다.

 

2) n > 1

- 매번 pasta[n] = NOT 인지 여부를 확인한다.

- 마음에 들진 않지만, 편하게 일일이 경우를 확인해서 dp[n][?] 의 값을 갱신시켜야 한다.

- 토마토, 크림, 바질에 대해, 연속으로 먹었을 때와 연속으로 먹지 않았을 때의 값을 각각 갱신한다.

- 전체 풀이 코드를 보면 이해하기 쉽다.

 

그리 어려운 문제는 아니라 설명은 짧게 하려 한다.

---

전체 풀이 코드는 다음과 같다.

#include <iostream>
using namespace std;

#define MAXN 101
#define MAXK 101
#define DIVIDER 10000

#define NOT 0
#define T   1
#define C   2
#define B   3
#define TT  4
#define CC  5
#define BB  6

#define MAXP 7

int dp[MAXN][MAXP];
int pasta[MAXK];

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

	int N, K; cin >> N >> K;
	while(K--) {
		int a, b; cin >> a >> b;
		pasta[a] = b;
	}

	if(pasta[1] == NOT) dp[1][T] = dp[1][C] = dp[1][B] = 1;
	else				dp[1][pasta[1]] = 1;

	for(int n=2; n<=N; n++) {
		if(pasta[n] == NOT) {
			dp[n][T] = (dp[n-1][C] + dp[n-1][B] +
						dp[n-1][CC] + dp[n-1][BB]) % DIVIDER;
			dp[n][TT] = dp[n-1][T];

			dp[n][C] = (dp[n-1][T] + dp[n-1][B] +
						dp[n-1][TT] + dp[n-1][BB]) % DIVIDER;
			dp[n][CC] = dp[n-1][C];

			dp[n][B] = (dp[n-1][T] + dp[n-1][C] +
						dp[n-1][TT] + dp[n-1][CC]) % DIVIDER;
			dp[n][BB] = dp[n-1][B];
		}
		else if(pasta[n] == T) {
			dp[n][T] = (dp[n-1][C] + dp[n-1][B] +
						dp[n-1][CC] + dp[n-1][BB]) % DIVIDER;
			dp[n][TT] = dp[n-1][T];
		}
		else if(pasta[n] == C) {
			dp[n][C] = (dp[n-1][T] + dp[n-1][B] +
						dp[n-1][TT] + dp[n-1][BB]) % DIVIDER;
			dp[n][CC] = dp[n-1][C];
		}
		else {
			dp[n][B] = (dp[n-1][T] + dp[n-1][C] +
						dp[n-1][TT] + dp[n-1][CC]) % DIVIDER;
			dp[n][BB] = dp[n-1][B];
		}
	}

	int ans = 0;
	for(int p=1; p<MAXP; p++) ans += dp[N][p];

	cout << (ans % DIVIDER) << '\n';

	return 0;
}