[백준] 14852번 타일 채우기3(시간초과 해결) - Java

[백준] 14852번 타일 채우기3 - Java

 

문제 출처

www.acmicpc.net/problem/14852

14852번: 타일 채우기 3

 

---

※ 풀이

이 문제의 경우도 2xn 타일 채우기와 유사한 응용문제이다.

 

동적계획법을 이용하여 점화식을 세워서 풀면 되는데 여러곳에 문제의 함정이 숨어있다...

 

먼저 점화식을 세우기 위해 규칙을 추론해보면

a[1]=2

a[2]=7

...

a[n]=2* a[n-1] + 3*a[n-2]+ (2* a[n-3]+ 2*a[n-4] + .... + 2*a[0] )

 

이런식의 결과가 나온다.

이유는 백준의 2133 번 타일채우기와 유사한 결과 인데 이렇게 식을 세워서 코드를 만들면 아래와 같이된다.

 

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

public class Main {

    static long[] arr = new long[1000001];

    public static void main(String[] args) throws IOException {
        //input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        System.out.println(dynamic(n));
    }

    static long dynamic(int idx) {
        if (idx == 0) return 1;     //불규칙한 값들
        else if(idx==1) return 2;
        else if(idx==2) return 7;       //초항 값들
        else if (arr[idx] != 0) {
            return arr[idx];
        } else {
            long a = 2 * dynamic(idx - 1);
            long b = 3 * dynamic(idx - 2);

            long sum = 0;
            for (int i = idx - 3; i >= 0; i--) {
                sum += 2 * dynamic(i) % 1000000007;
            }

            return arr[idx] = (a + b + sum) % 1000000007;
        }
    }
}

그런데 이렇게 코드를 만들고 제출하면....

 

시간 초과가 뜬다...

 

결과를 보고 잠깐 뇌정지가 와서 혼란스러웠지만 잘 생각해보면

2133 번 타일채우기 문제는 n 이 1~30 사이의 값이기 때문에 저런식으로 코드를 짜도 문제가 없었지만

이번 문제의 경우 주어지는 n 의 범위가 무려  N(1 ≤ N ≤ 1,000,000) 사이이기 때문에 안되는 것이였다.

 

결론은 더 빡센 최적화가 필요하다는 것인데

sum 을 구하는 과정의 값들도 동적계획법을 이용하여 값을 저장해놓고 가져다 쓰는 것이 필요하다.

때문에 이차원 배열을 미리 만들어 놓고 아래와 같이 코딩하면 답을 구할 수 있다.

(a[n][1] 부분에 그 전까지의 합을 미리 구해놓고 가져다 쓰는 방식이다)

 

---

※ 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static long[][] arr = new long[1000001][2];

    public static void main(String[] args) throws IOException {
        //input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        System.out.println(dynamic(n));
    }

    static long dynamic(int idx) {
        arr[0][0] = 0;
        arr[1][0] = 2;
        arr[2][0] = 7;
        arr[2][1] = 1;

        for (int i = 3; i <= idx; i++) {
            arr[i][1] = (arr[i - 1][1] + arr[i - 3][0]) % 1000000007;
            arr[i][0] = (3 * arr[i - 2][0] + 2 * arr[i - 1][0] + 2 * arr[i][1]) % 1000000007;
        }
        return arr[idx][0];
    }
}

---