[백준]_20544_공룡게임

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

def sol(n, now, before):
    global MOD_NUM
    if n == 0:
	// 처음에 시작 높이 1
        if now == 0:
            dp[n][now][before] = 1
        else:
            dp[n][now][before] = 0
        return dp[n][now][before]

    if dp[n][now][before] == -1:
        a1, a2, a3 = 0, 0, 0

	// 높이가 0일 경우 다음꺼 상관x
        if now == 0:
            a1 = sol(n - 1, 0, now)% MOD_NUM
            a2 = sol(n - 1, 1, now)% MOD_NUM
            a3 = sol(n - 1, 2, now)% MOD_NUM
        elif now == 1: //현재 1
            if before == 0: // 이전 높이가 0이면 아무거나 올 수 있다.
                a1 = sol(n - 1, 0, now)% MOD_NUM
                a2 = sol(n - 1, 1, now)% MOD_NUM
                a3 = sol(n - 1, 2, now)% MOD_NUM
            else: // 아니면 다음 높이는 무조건 0
                a1 = sol(n - 1, 0, now)% MOD_NUM
        else: // 2일 때
            if before == 0: // 2가 연속으로 올 수 없음
                a1 = sol(n - 1, 0, now)% MOD_NUM
                a2 = sol(n - 1, 1, now)% MOD_NUM
            else:
                a1 = sol(n - 1, 0, now)% MOD_NUM

        dp[n][now][before] = (a1 + a2 + a3) % MOD_NUM

    return dp[n][now][before]


def exp(n, now, before):
    global MOD_NUM
    if n == 0:
        if now == 0:
            ex[n][now][before] = 1
        else:
            ex[n][now][before] = 0
        return ex[n][now][before]

    if ex[n][now][before] == -1:
        a1, a2 = 0, 0

        if now == 0:
            a1 = exp(n - 1, 0, now)% MOD_NUM
            a2 = exp(n - 1, 1, now)% MOD_NUM
        else:
            if before == 0:
                a1 = exp(n - 1, 0, now)% MOD_NUM
                a2 = exp(n - 1, 1, now)% MOD_NUM
            else:
                a1 = exp(n - 1, 0, now)% MOD_NUM

        ex[n][now][before] = (a1 + a2) % MOD_NUM

    return ex[n][now][before]


import sys
sys.setrecursionlimit(2000)
MOD_NUM = 1000000007
N = int(input())

dp = [[[-1 for i in range(3)] for i in range(3)] for i in range(N)]
ex = [[[-1 for i in range(2)] for i in range(2)] for i in range(N)]

alls = sol(N - 1, 0, 0) + sol(N - 1, 1, 0) + sol(N - 1, 2, 0)
exception = exp(N - 1, 0, 0) + exp(N - 1, 1, 0)

print((alls - exception) % MOD_NUM)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class B20544 {
	static int T, MOD = 1000000007;
	static long[][][] arr, exps;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		//i는 위치, j는 전꺼 k는 현재 높이
		arr= new long[T+1][3][3];
		for(long first[][]:arr) {
			for(long second[]:first) {
				Arrays.fill(second, -1L);
			}
		}
		exps= new long[T+1][2][2];
		for(long first[][]:exps) {
			for(long second[]:first) {
				Arrays.fill(second, -1L);
			}
		}
		
		long all = (solve(T - 1, 0, 0) + solve(T - 1, 1, 0) + solve(T - 1, 2, 0)) % MOD;
		long excep = (exception(T - 1, 0, 0) + exception(T - 1, 1, 0)) % MOD;
		System.out.println((excep)%MOD);
	}
	
	
	private static long solve(int n, int now, int before) {
		if (arr[n][now][before] != -1)
			return arr[n][now][before];
		
		if (n == 0){
			if (now == 0)
				arr[n][now][before] = 1;
			else
				arr[n][now][before] = 0;
			return arr[n][now][before];
		}

		if (now == 0){
			return (solve(n - 1, 2, now) + solve(n - 1, 1, now) + solve(n - 1, 0, now))%MOD;
		}
		else if (now == 1){
			if (before == 0)
				return (solve(n - 1, 2, now) + solve(n - 1, 1, now) + solve(n - 1, 0, now))%MOD;
			else
				return solve(n - 1, 0, now)%MOD;
		}
		else if (now == 2){
			if (before == 0)
				return (solve(n - 1, 1, now) + solve(n - 1, 0, now))%MOD;
			else if (before == 1)
				return solve(n - 1, 0, now)%MOD;
		}
		return arr[n][now][before]%MOD;
	}

	
	private static long exception(int n, int now, int before) {
		
		if (exps[n][now][before] != -1)
			return exps[n][now][before];
		
		if (n == 0)
		{
			if (now == 0)
				exps[n][now][before] = 1;
			else
				exps[n][now][before] = 0;
			return exps[n][now][before];
		}

		if (now == 0){
			return (exception(n - 1, 1, now) + exception(n - 1, 0, now)) % MOD;
		}
		else if (now == 1){
			if (before == 0)
				return (exception(n - 1, 1, now) + exception(n - 1, 0, now)) % MOD;
			else if (before == 1)
				return exception(n - 1, 0, now) % MOD;
		}
		return exps[n][now][before]%MOD;
	}
}