백준 5546 _ 파스타

www.acmicpc.net/problem/5546

5546번: 파스타

---

✨ 내 소스 코드

#include<iostream>
#include <string>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int a[101] = { 0, }, dp[101][4][4] = { 0, };
	int N, K;

	cin >> N >> K;

	while (K--) {
		int t1, t2;
		cin >> t1 >> t2;
		a[t1] = t2;
	}

	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			if (a[1]!=0 && i != a[1]) 
				continue;
			if (a[2]!=0 && j != a[2]) 
				continue;
			dp[2][i][j] = 1;
		}
	}

	for (int i = 3; i <= N; i++) {
		for (int j = 1; j <= 3; j++) {
			if (a[i]!=0 && j != a[i]) 
				continue;
			for (int k = 1; k <= 3; k++) {
				if (a[i - 1] != 0 && k != a[i - 1])
					continue;
				for (int l = 1; l <= 3; l++) {
					if (j != k || j != l) {
						dp[i][k][j] = (dp[i][k][j] + dp[i - 1][l][k]) % 10000;
					}
					
				}
			}
		}
	}
    
	int result = 0;
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			result = (result + dp[N][i][j]) % 10000;
		}
	}
	cout << result;
	return 0;
}

 

🙏 문제 풀이

dp [n 일째][n-1일째 음식][n 일째 음식] = 경우의 수

와 같은 dp 배열로 문제를 해결하였다

 

백준에 있는 예시로 알고리즘을 한 번 풀이해보면

1일째에는 1번 파스타, 3일째에는 1번 파스타, 4일째에는 2번 파스타라고 지정이 되어있다

 

1일째는 1번으로 세팅이 되어있기 때문에, dp [2일째][1일째 음식=1][2일째 음식]만 dp에 값이 저장될 것이다

2일째 음식은 정해져 있지 않으므로, 올 수 있는 값은 1, 2, 3이고 경우는 각각 1개이기 때문에

아래와 같이 dp에 저장된다

그 외에는 배열 초기화로 인해 0으로 값이 저장되어있다

그다음인 3일 째를 살펴보면, 3일째의 음식은 1번 파스타로 고정이 되어있다

따라서 dp[3일째][2일째 음식][3일째 음식=1]만 dp에 값이 저장 될 것이고

2일째 음식으로 올 수 있는 것은 1, 2, 3 총 3가지가 가능하다

이때, 2일째의 파스타가 1번이 될 경우 1 1 1로 3일 동안 같은 파스타를 먹는 경우가 되므로, 이는 배재시켜준다(if (j != k || j!= l))

나머지도 동일하게 진행되어 최종적으로 6이라는 값이 도출된다

 

 

⭐ 문제 풀이 결과