[1904번] 01타일 JAVA☕

 

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

1904번: 01타일

 

---

알고리즘 [접근 방법]

이 문제는 만약 N=1 부터 경우의 수를 쭉 나열해보았다면 매우 쉽게 풀 수 있다.

N=6까지 가능한 경우의 수를 나열해보았다.
개수가 피보나치 수의 수열처럼 증가하고 있음을 알 수 있다.
즉, N=3일 때는 N=1, N=2일 때의 개수의 합이다.
이는 피보나치 점화식과 일치함을 알 수 있다.

---

풀이

static int[] dp = new int[size];    // 배열 비어있는 표시는 -1 이라고 가정
 
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
 
int Tile(int N) {
    if(dp[N] == -1) {    // 해당 배열에 값이 없을경우 재귀호출
        dp[N] = Tile(N - 1) + Tile(N - 2);
     }
    return dp[N];
}

[주의할 점]
int[] 배열은 디폴트값이 0으로 되어있으므로 모든 배열을 -1로 초기화해줄 필요가 있다.
Integer 배열로 풀이하는 방법도 있으나 입력 값이 1,000,000이라 잘못하면 메모리 부족으로 stackoverflow 에러를 내뱉을 수 있다. 그리고 현재, 경우의 수를 15746으로 나눈 값, 즉 DP[N] % 15746 을 출력해야만 한다.

전체적인 구조는 아래와 같다.

static int[] dp = new int[size];    // 배열 비어있는 표시는 -1 이라고 가정
 
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
 
int Tile(int N) {
    if(dp[N] == -1) {    // 해당 배열에 값이 없을경우 재귀호출
        dp[N] = (Tile(N - 1) + Tile(N - 2)) % 15746;
     }
    return dp[N];
}

여기서 또 하나 주의할 점은, 각 배열에 나머지값을 저장하면 다른 재귀에서 해당 값을 쓰게될 때, 나머지 값을 쓰게되는데 그러면 원래 값의 나머지와 달라질 수 있다고 생각할 수 있다.

 

이 부분은 모듈러 연산의 분배법칙을 이해하면 쉽다.

 

즉,  (A+B) % C = (A%C + B%C) % C 가 성립한다는 것이다.

결과적으로는 효율적인 방법은 아니다. 시간복잡도는 이론적으로 O(N)이라 하지만 매 재귀마다 조건문을 검사하는 등 오버헤드가 커질 수 밖에 없을 것이다. 그래서 반복문으로 푸는 것이 더욱 효율적이다.

---

코드

package com.linerate;
 
import java.util.Scanner;
 
public class Main {
 
    public static int[] dp = new int[1000001];;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
 
        int N = in.nextInt();
 
 
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
 
        // -1 로 초기화
        for(int i = 3; i < dp.length; i++) {
            dp[i] = -1;
        }
 
        System.out.println(Tile(N));
 
    }
 
    public static int Tile(int N) {
 
        if(dp[N] == -1) {
            dp[N] = (Tile(N - 1) + Tile((N - 2))) % 15746;
        }
        return dp[N];
    }
 
}