[Java][백준] 1904번 01타일

1904번: 01타일

---

아이디어

1. 먼저 n=1, 2, 3, 4... 를 구해봤다

// n=1이면 1
// n=2, 00 11
// n=3, 001, 100, 111
// n=4, 0011, 1001, 0000, 1100, 1111
// n=5, 00001, 00100, 10000, 11100, 10011, 11001, 00111, 11111
// n=6, 000000, 001001, 001100, 000011, 100100, 100001, 110000 ....

 

tile[1] = 1

tile[2] = 2

tile[3] = 3

tile[4] =5

.

.

.

tile[n] = tile[n-1] + tile[n-2]

1904번 문제는 피보나치 수열 알고리즘이다!

 

2. 코드를 구현해주면 된다

 

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

        BufferedReader bufferedReader =  new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());

        int result = tile(n)%15746;
        System.out.println(result);
    }

    public static int tile(int n) {
        if (n<=2) { return n; }
        return tile(n-1) + tile(n-2);
    }
}

 

2-1. 문제 키워드가 동적 프로그래밍인 걸 깜빡했다... 시간 초과가 나왔다.

3. 동적 프로그래밍으로 구현해준다.

 

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

        BufferedReader bufferedReader =  new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());

        int[] dp = new int[Math.max(n + 1, 3)];

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
        } 

        System.out.println(dp[n]);
    }
}

 

• 피보나치 수열과 다르게 n=2까지는 dp[n] = dp[n-2] + dp[n-1]이 적용되지 않으므로 미리 정의 내려줘야 한다.
• n=3부터는 dp[n] = dp[n-2] + dp[n-1]를 계산한다.

 

+)

 

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 2 
out of bounds for length 2

 

• 0, 1을 입력할 때 이 오류를 정말 많이 봤는데, 알고보니까 배열 길이를 이미 dp[2]까지 3개를 저장해둬서 배열의 최소 길이가 3이어야 했던 것..
• Solution:

int[] dp = new int[Math.max(n + 1, 3)];

 

• n+1, 3 둘 중에 더 큰 값을 선택해서 배열 길이를 정의하기로 했다.
• 3은 n = 0, 1, 2 입력 시 최소 배열 길이인 3을 충족하기 위한 수