[BOJ 1904] 01타일 (Java, DP)

 

 

---

문제 링크

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

1904번: 01타일

---

문제 풀이 

- 00, 1 이 주어지고, N 자리 수 만큼의 2진 수열 개수를 구하는 문제 

- N = 1,000,000 인 경우 int[] DP = new int[N + 1] 했을 때 배열 자리수 하나당 4byte 차지하므로 4MB 용량 차지 (제한 256MB)

- 상향식 방식으로 풀이하여 O(N) 시간복잡도 소요됨

 

초기화 DP

0	1	2	...
0	1	2	...

 

N = 1 의 경우 

1 

 

N = 2의 경우 

11 

00 

 

N = 3의 경우 

111

001

100

 

N = 4의 경우 

1111

0011

1001

1100

0000

 

N = 4의 경우 N - 1(3) 에 1을 붙이는 경우와 N - 2에 00 타일을 붙이는 경우를 생각하여 더하면 중복 없이 구할 수 있다. 
결국 초기값이 조금 다른 피보나치 수열이었다

---

제출 코드

초기화시 실수하여 ArrayIndexOutOfBoundException이 발생한게 아닌가 유추 

import java.util.*;
import java.io.*;

public class Main {
    
    static int N;
    static int[] DP;
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        DP = new int[N + 1];

        for(int i = 1; i <= N; i++) {
            if(i == 1) DP[i] = 1;
            else if(i == 2) DP[i] = 2;
            else DP[i] = (DP[i - 1] + DP[i - 2]) % 15746;
        }

        br.close();
    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(DP[N]);
    }
}