[구름 알고리즘 먼데이 챌린지] Week4 : 3. 거리두기

문제

 

구름이는 구름카페를 운영하는 사장님이다. 구름카페에는 아래 그림처럼 한 줄에 3개의 테이블이 있고, 이러한 줄이 총 N

줄 배치되어 있다.

기존에는 모든 테이블에 동시에 사람들이 앉을 수 있었다. 하지만 사람들 사이에서 소음으로 자주 다툼이 발생하자, 구름이는 테이블 간 거리두기를 시행해서 일부 테이블에서만 앉아서 커피를 마시거나 작업을 할 수 있도록 하려고 한다. 테이블 간 거리두기를 시행하게 되면 어떤 사람이 앉아있는 자리에서 앞뒤와 양옆으로 인접한 테이블에는 동시에 사람들이 앉을 수 없게 된다.
구름이는 거리두기 방식에 따라, 사람들이 앉을 수 있는 테이블에 스티커를 붙이기로 했다. 구름이는 충분히 많은 스티커를 가지고 있기 때문에 붙일 수 있는 스티커의 개수에는 제한이 없으며, 스티커를 하나도 붙이지 않는 경우도 있다.

구름카페에 있는 테이블의 줄 수 N이 주어졌을 때, 구름이가 테이블에 스티커를 붙일 수 있는 경우의 수를 구해보자. 단, 수가 너무 커질 수 있으므로 경우의 수를 100,000,007로 나눈 나머지를 출력한다.

---

 

---

문제를 읽고 DP(Dynamic Programming)알고리즘 분류의 문제라고 생각하고 바로 점화식을 찾고자 했다.

이를 위해 먼저, N = 1인 경우 가능한 경우를 생각해보면 아래와 같다.

N = 1 : dp[1][1](□ □ □) = 1, dp[1][2](■ □ □) = 1, dp[1][3](□ ■ □) = 1, dp[1][4](□ □ ■) = 1, dp[1][5](■ □ ■) = 1  -> 총 5가지

-> dp[N][1~5] : N번째 줄에 각각 1~5 가 가능한 경우의  수를 저장.

이제 위에 5가지를 각각 하나의 블록으로 생각하면 다음 N=2 번째 줄에 가능한 경우의 수를 판단하는 것은 어렵지 않다.

문제 조건에 따르면,

dp[2][1](□ □ □) : N-1번 줄에 1~5까지 어떤 블록이 놓였어도 현재 N번 째 줄에 1번 불록을 놓는 것이 가능

따라서, 2번째 줄에 1번 불록을 놓을 수 있는 경우의 수는 dp[1][1]+dp[1][2]+dp[1][3]+dp[1][4]+dp[1][5] = 5

dp[2][2](■ □ □) : N-1번 줄에 □ □ □(1) □ ■ □(3) □ □ ■(4) 블록인 경우 -> dp[1][1]+dp[1][3]+dp[1][4] = 3

dp[2][3](□ ■ □) : N-1번 줄에 □ □ □(1) ■ □ □(2) □ □ ■(4) ■ □ ■(5) 블록인 경우 -> dp[1][1]+dp[1][2]+dp[1][4]+dp[1][5] = 4

dp[2][4](□ □ ■) : N-1번 줄에 □ □ □(1) ■ □ □(2) □ ■ □(3) 블록인 경우 -> dp[1][1]+dp[1][2]+dp[1][3] = 3

dp[2][5](■ □ ■) : N-1번 줄에 □ □ □(1) □ ■ □(3) 블록인 경우 -> dp[1][1]+dp[1][3] = 2

 

아래는 직접 점화식을 구하기 위해 그려본 과정이다.

다시 한번 점화식을 요약하면 아래와 같다.

dp[n][1] = DP(n-1, 1) + DP(n-1, 2) + DP(n-1, 3) + DP(n-1, 4) + DP(n-1, 5)

dp[n][2] = DP(n-1, 1) + DP(n-1, 3) + DP(n-1, 4)

dp[n][3] = DP(n-1, 1) + DP(n-1, 2) + DP(n-1, 4) + DP(n-1, 5)

dp[n][4] = DP(n-1, 1) + DP(n-1, 2) + DP(n-1, 3)

dp[n][5] = DP(n-1, 1) + DP(n-1, 3)

 

즉, 각 줄의 1번부터 5번 블록의 경우의 수를 d[n][0], d[n][1], d[n][2], d[n][3], d[n][4] 배열에 메모리제이션 해주고 DP알고리즘으로 계산을 최소화 해주는 것이다.  

 

한가지 주의할 점으로 입력 조건에 N이 100,000 까지 이므로 변수 타입을 long long으로 해주고 마지막 최종 경우의 수를 출력할 때를 제외하고도 계산하는 과정에서도 오버플로우를 방지하기 위해 마찬가지로 모듈러연산을 해주어야 한다.

 

#include <iostream>
using namespace std;

int n;
long long ans, dp[100001][5];
long long DP(int x, int idx) {
	if (x == 1) return 1;
	if (dp[x][idx]) return dp[x][idx];
	else if (idx == 0) {
		for (int i = 0; i < 5; i++)
			dp[x][idx] += DP(x - 1, i);
		return dp[x][idx] %= 100000007;
	}
	else if (idx == 1)
		return dp[x][idx] = (DP(x - 1, 0) + DP(x - 1, 2) + DP(x - 1, 3)) % 100000007;
	else if (idx == 2)
		return dp[x][idx] = (DP(x - 1, 0) + DP(x - 1, 1) + DP(x - 1, 3) + DP(x - 1, 4)) % 100000007;
	else if (idx == 3)
		return dp[x][idx] = (DP(x - 1, 0) + DP(x - 1, 1) + DP(x - 1, 2)) % 100000007;
	return dp[x][idx] = (DP(x - 1, 0) + DP(x - 1, 2)) % 100000007;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < 5; i++) ans += DP(n, i);
	cout << ans % 100000007;
	return 0;
}