자바로 백준 1904 풀기

• 실버 4단계 문제

풀이)

재귀처럼 작은 문제를 큰 문제로 확장하는 방법을 쓰되, 중복계산을 줄이기 위해 이전에 계산했던 값을 저장하는 DP 방식으로 풀어야 한다.

내 코드)

import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int n = Integer.parseInt(br.readLine());

    long[] tile = new long[1000001];

    tile[1] = 1; tile[2] = 2; tile[3] = 3;
    if(n > 3) {
      for(int i = 3; i <= n; i++) {
        tile[i] = tile[i-1] + tile[i-2];
        tile[i] %= 15746;
      }
    }
    bw.write(String.valueOf(tile[n]));

    bw.flush();
    bw.close();
  }
}