[BOJ] BOJ_1904 01타일 (JAVA)

[문제 - 1904번: 01타일 (JAVA)]

[접근 방법]

다이나믹 프로그래밍을 이용하여 문제를 해결하려고 한다.

N = 1 - 1가지 (1)

N = 2 - 2가지 (00, 11)

N = 3 - 3가지 (100, 001, 111)

N = 4 - 5가지 (0000, 0011, 1100, 1001, 1111)

N = 5 - 8가지 (00001, 00100, 00111, 10000, 10011, 11001, 11100, 11111)

 

N >= 3 에 대하여, [N=N 인 경우] = [N-1 인 경우] + [N-2 인 경우] 가 성립한다는 것을 알 수 있다.

이와 같은 관계식으로 DP 문제를 해결하고자 한다.

[JAVA 코드]

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

public class BOJ_1904 {

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    //지원이가 만들 수 있는 길이 : N
    int N = Integer.parseInt(br.readLine());
    
    int[] DP = new int[N+3];
    Arrays.fill(DP, 0); //배열 초기화
    DP[1] = 1;
    DP[2] = 2;
    
    
    for (int i = 3; i <= N; i++) {
      DP[i] = (DP[i-1] + DP[i-2]) % 15746;
    }
    


    bw.write(DP[N] + " ");
  
    bw.flush();
    bw.close();
  }
}

 

[Rewind]

1. 어려웠던 점

1) DP 관계식을 생각해내는 과정

2) DP[] 배열의 크기를 설정하는 방법

: DP[] 배열의 크기를 N+1 로 설정할 경우,

N = 1 이 된다면, DP[i-1]  , DP[i-2] 에서 DP[-1], DP[0] 이 됨으로 " 런타임 에러 (ArrayIndexOutOfBounds) " 가 발생한다.

N = 2 일 경우도 마찬가지..

 

2. 알게된 점

DP[] 배열의 크기 설정 기준에 대해 다시 한번 깨닫게 됨.

DP 문제에 대해 조금 더 익숙하게 됨.

 

3. 개선 방안

더 많은 DP 문제를 접함으로서, 해결 노하우를 축적해 나갈 필요가 있음.