문제는 다음과 같다.
예제는 다음과 같다
입력
4출력
41
자세한 문제는 직접 가서 보자.
https://www.acmicpc.net/problem/1309
우리는 경우에 수에 대해 다음과 같이 생각할 수 있다.
- 사자가 없을 때
- 사자가 왼쪽에 있을 때
- 사자가 오른쪽에 있을 때
이를 DP배열로 나타내면 다음과 같다.
- dp[1][0] = 비어있음
- dp[1][1] = 왼쪽에 있음
- dp[1][2] = 오른쪽에 있음
이를 통해 초기 경우의 수를 배열에 각각 저장하면 초기값은 다음과 같다.
- dp[1][0] = 1
- dp[1][1] = 1
- dp[1][2] = 1
그렇다면 두 번째 순서부터 어떻게 해야할까
dp[2][0]부터 알아보자.
dp[2][0]은 두번째 순서에서 비어있는 경우이다.
이때 우리는 이전 순서에서 비어있어도 되고, 왼쪽에 있어도 되고, 오른쪽에 있어도 모두 가능한 경우의 수를 만들 수 있다. 그런고로 dp[2][0]는 다음과 같다.
dp[2][0] = dp[1][0] + dp[1][1] + dp[1][2]
그리고 문제에 요구하는 9901로 나머지를 출력해야하기 때문에 결과적으로는
dp[2][0] = (dp[1][0] + dp[1][1] + dp[1][2]) % 9901
이 된다.
그 다음 dp[2][1]은 어떨까
dp[2][1]은 왼쪽에 있는 경우를 의미한다.
dp[2][1]에 있는 경우는 이전 순서에서 비어있거나 오른쪽에 있어야만 현재 순서에서 왼쪽에 있는 경우의 수를 구할 수 있다. 그런고로 dp[2][1]은 다음과 같다.
dp[2][1] = dp[2][0] + dp[2][2]
그리고 문제에 요구하는 9901로 나머지를 출력해야하기 때문에 결과적으로는
dp[2][1] = (dp[2][0] + dp[2][2]) % 9901
마지막으로 dp[2][2]를 알아보자
dp[2][2]는 오른쪽에 있는 경우를 의미한다.
dp[2][2]에 있는 경우는 이전 순서에서 비어있거나 왼쪽에 있어야만 현재 순서에서 오른쪽에 있는 경우의 수를 구할 수 있다. 그런고로 dp[2][1]은 다음과 같다.
dp[2][2] = dp[2][0] + dp[2][1]
그리고 문제에 요구하는 9901로 나머지를 출력해야하기 때문에 결과적으로는
dp[2][2] = (dp[2][0] + dp[2][1]) % 9901
이를 모두 정리하면 다음과 같은 점화식이 나온다.
- dp[i][0] = (dp[i][0] + dp[i][1] + dp[i][2]) % 9901
- dp[i][1] = (dp[i][0] + dp[i][2]) % 9901
- dp[i][2] = (dp[i][0] + dp[i][1]) % 9901
이를 모두 더하면 모든 경우의 경우의 수를 구할 수 있고 문제의 정답이 된다.
코드는 다음과 같다.
public class Main {
static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
dp = new int[n + 1][3];
dp[1][0] = dp[1][1] = dp[1][2] = 1;
for(int i = 2; i <= n; i++) {
dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 9901;
dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % 9901;
dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % 9901;
}
long ans = (dp[n][0] + dp[n][1] + dp[n][2]) % 9901;
System.out.println(ans);
}
}
끝!
