[백준]1904번: 01타일

풀이

해당 코드는 dp 문제이다.
점화식을 찾는 것이 중요하다.

N=1, 1 => 1가지
N=2, 00, 11 => 2가지
N=3, 001, 100, 111 => 3가지
N=4, 0000, 0011, 1001, 1100, 1111 => 5가지
N=5, 00001, 00100, 10000, 00111, 10011, 11001, 11100, 11111 => 8가지
N=6, 000000, 000011, 001001, 100001, 001100, 100100, 110000, 001111, 100111, 110011, 111001, 111100, 111111 => 13가지


피보나치 수열 dp[N] = dp[N-1] + dp[N-2]

틀린 코드

시간 초과 => 재귀 반복

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

public class Main {
    static int N;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new int[N + 1];
        dp[0] = 0;

        System.out.println(cal(N));
    }

    private static int cal(int num) {
        if (num == 1) {
            return 1;
        } else if (num == 2) {
            return 2;
        } else {
            dp[num] = (cal(num - 1) + cal(num - 2)) % 15746;
            return dp[num];
        }
    }

}

런타임 에러 => N=1일 경우 dp[2] 인덱스 범위 초과

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1];
        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]);
    }
}

정답 코드

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

public class Main {
    static int N;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new int[N + 1];
        dp[0] = 0;

        System.out.println(cal(N));
    }

    private static int cal(int num) {
        if (dp[num] != 0) {  // 이미 계산된 값이 있는 경우 추가
            return dp[num];
        }

        if (num == 1) {
            return dp[1] = 1;
        } else if (num == 2) {
            return dp[2] = 2;
        } else {
            dp[num] = (cal(num - 1) + cal(num - 2)) % 15746;
            return dp[num];
        }
    }
}

• 재귀 함수일 때는 호출이 계속 되므로 시간 초과가 날 수 있다.
• 값이 이미 있으면 재귀 호출을 하지 않도록 설정한다.