[백준 2780] 비밀번호 - JAVA

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

 

dp + 노가다

좀 더 귀찮아지지만, list 순회보다 dp점화식에 바로 적용하는 것이 더 빠르다.

 

n = 0~9일 때,

dp[i][n] = SUM(dp[i-1][n에 인접한 수])

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

class Main {

  public static void main(String[] args) throws IOException {

    List<Integer>[] l = new ArrayList[10];

    for (int i = 0; i < 10; i++) {
      l[i] = new ArrayList<>();
    }

    l[0].add(7);
    l[1].add(2);
    l[1].add(4);
    l[2].add(1);
    l[2].add(3);
    l[2].add(5);
    l[3].add(2);
    l[3].add(6);
    l[4].add(1);
    l[4].add(5);
    l[4].add(7);
    l[5].add(2);
    l[5].add(4);
    l[5].add(6);
    l[5].add(8);
    l[6].add(3);
    l[6].add(5);
    l[6].add(9);
    l[7].add(0);
    l[7].add(4);
    l[7].add(8);
    l[8].add(5);
    l[8].add(7);
    l[8].add(9);
    l[9].add(6);
    l[9].add(8);

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());
    int MOD = 1234567;
    int[][] dp = new int[1000][10];

    for (int i = 0; i < 10; i++) {
      dp[0][i] = 1;
    }

    for (int i = 1; i < 1000; i++) {
      for (int j = 0; j < 10; j++) {
        List<Integer> near = l[j];

        for (int k = 0; k < near.size(); k++) {
          dp[i][j] += dp[i - 1][near.get(k)];
          dp[i][j] %= MOD;
        }
      }
    }
    while (T-- > 0) {
      int N = Integer.parseInt(br.readLine());

      int ans = 0;
      for (int i = 0; i < 10; i++) {
        ans += dp[N - 1][i];
        ans %= MOD;
      }
      System.out.println(ans);
    }
  }
}