21.09.15 기록

백준 알고리즘 1904 풀이

🎆해설

-문제 자체가 이해가 안되서 못하다가, 이해를 해도 못하겠어서 그냥 해설을 봤다.
-N개의 2진 수열 개수가 피보나치 수의 수열처럼 증가하고 있어 이를 응용하여 풀면 되는 문제였다.
-확실히 재귀를 사용하지 않는 두번째 풀이가 더 빨랐다.

//(1) 동적계획법을 사용한 풀이(메모리 52.8MB, 시간 332ms로 통과)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B1904 {
    public static int[] dp = new int[1_000_000 + 1];

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

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

        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];
    }
}

//(2) 반복문을 사용한 풀이(메모리 14.2MB, 시간 136ms로 통과)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B1904 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(tile(N));
    }

    public static int tile(int N) {
        if(N == 1) { return 1; }
        if(N == 2) { return 2; }

        int val1 = 1;
        int val2 = 2;
        int sum = 0;
        for(int i = 2; i < N; i++) {
            sum = (val2 + val1) % 15746;
            val1 = val2;
            val2 = sum;
        }

        return sum;
    }
}