[Algo] 백준 25421 조건에 맞는 정수의 개수 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/25421

메모리 : 20892KB

시간 : 160ms

언어 : Java 11

---

코드

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long[][] dp = new long[100001][6];
        Arrays.fill(dp[1], 1);
        int mod = 987654321;
        for (int i = 2; i < 100001; i++) {
            dp[i][1] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % mod;
            dp[i][2] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4]) % mod;
            dp[i][3] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5]) % mod;
            dp[i][4] = (dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5] + dp[i - 1][4]) % mod;
            dp[i][5] = (dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5] + dp[i - 1][4] + dp[i - 1][3]) % mod;
        }
        int ans = 0;
        for (int i = 1; i < 5; i++) {
            ans += dp[N][i];
            ans %= mod;
        }
        ans = ans * 2 % mod;
        ans += dp[N][5];
        ans %= mod;
        System.out.println(ans);

    }
}

풀이

1부터 9까지 [3,4,5,5,5,5,5,4,3] 순으로 경우의 수를 가질 수 있다. 또한 5를 기준으로 양쪽이 대칭된다. 이를 이용해 메모이제이션을 해 문제를 풀 수 있다.