[백준 24464] 득수 밥 먹이기 (C++)

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

 

문제

---

프로젝트 하느라 바쁜 득수는 밥 먹을 시간이 부족하다. 그래서 주로 찾는 식당 네 개 중 하나에서 하루에 한 번 밥을 먹는다. 귀찮으면 굶을 때도 있다.

 

늘 새로운 느낌을 받고 싶었던 득수는 다음과 같은 규칙으로 다음날 갈 식당을 정한다.

• 첫날에는 굶거나, 임의로 원하는 식당 하나를 골라서 간다.
• 어제 굶지 않았다면, 오늘은 식당을 가지 않아도 된다.
• 어제 식당을 가지 않았다면, 오늘은 식당을 가서 밥을 먹어야 한다.
• 오늘 간 식당은 다음날 가지 않는다.
• 오늘 간 식당과 이웃한 식당은 다음날 가지 않는다.

만약 2번 식당을 오늘 갔다면, 다음날 1, 2, 3번 식당은 가지 않는다. 따라서 새로운 느낌을 받으려면 4번 식당을 가거나 굶어야 한다.

득수가 𝑁일 치 식단표를 만들려고 한다. 위 규칙을 따라 식단표를 만들 때 가능한 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄에는 득수가 만들어야 하는 점심 식단의 총 날짜 𝑁이 입력으로 들어온다. (1 ≤ 𝑁 ≤ 200,000) 

 

출력

---

 𝑁일 치 식단표를 만들 때 가능한 경우의 수를 1000000007( = 10⁹ + 7)로 나눈 나머지를 출력한다.

 

문제 풀이

---

dp 문제.

각 경우의 수를 저장하는 2차원 dp 배열을 생성한다. dp[i][0]은 i번째 날에 굶은 경우, dp[i][1]~dp[i][4]는 각각 i번째 날에 1~4번 식당에서 밥을 먹은 경우라고 정의한다.

오늘 굶으려면 어제 굶지 않아야 한다. 즉, 1번, 2번, 3번, 4번 식당에서 밥을 먹은 상태여야 한다. 따라서 굶은 경우 dp[i][0] = dp[i - 1][1] + dp[i-1][2] + dp[i - 1][3] + dp[i - 1][4]가 성립한다.

어제 먹은 식당과 이웃한 식당은 오늘 가지 않으므로 오늘 1번 식당에서 밥을 먹으려면 어제 굶거나, 3번, 4번 식당에서 밥을 먹은 상태여야 한다. 따라서 dp[i][1] =dp[i - 1][0] + dp[i - 1][3]+dp[i-1][4]가 성립한다.

마찬가지로 오늘 2번 식당에서 밥을 먹으려면 어제 굶거나, 4번 식당에서 밥을 먹은 상태여야 한다. 따라서 dp[i][2] = dp[i - 1][0] + dp[i - 1][4]가 성립한다.

오늘 3번 식당에서 밥을 먹으려면 어제 굶거나, 1번 식당에서 밥을 먹은 상태여야 한다. 따라서 dp[i][3] = dp[i - 1][0] + dp[i - 1][1]가 성립한다.

오늘 4번 식당에서 밥을 먹으려면 어제 굶거나, 1번, 2번 식당에서 밥을 먹은 상태여야 한다. 따라서 dp[i][4] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]가 성립한다.

dp[i][0]부터 dp[i][4]까지 모두 더하면 i번째 날짜까지 가능한 경우를 모두 구할 수 있다.

 

아래는 코드.

#include <iostream>
using namespace std;

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

	int N;
	cin >> N;
	long long** dp = new long long*[N];
	for (int i = 0; i < N; i++)
	{
		dp[i] = new long long[5];
		for (int j = 0; j < 5; j++)
		{
			dp[i][j] = 0;
		}
	}
	dp[0][0] = 1;
	dp[0][1] = 1;
	dp[0][2] = 1;
	dp[0][3] = 1;
	dp[0][4] = 1;
	for (int i = 1; i < N; i++)
	{
		dp[i][0]= (dp[i - 1][1] + dp[i-1][2] + dp[i - 1][3] + dp[i - 1][4]) %1000000007;
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][3]+dp[i-1][4]) % 1000000007;
		dp[i][2] = (dp[i - 1][0] + dp[i - 1][4]) % 1000000007;
		dp[i][3] = (dp[i - 1][0] + dp[i - 1][1]) % 1000000007;
		dp[i][4] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 1000000007;
	}
	cout << (dp[N - 1][0] + dp[N - 1][1] + dp[N - 1][2] + dp[N - 1][3] + dp[N - 1][4]) % 1000000007 << "\n";
	return 0;
}