[백준] 1904번 01타일 _ JAVA ( 주석 설명 )

1번

→ 규칙을 찾아보면 피보나치 수열과 같아, 동일한 방식으로 접근해 풀면 되는 문제

→ Top-down 방식 (Intellij 에서는 StackOverflow 가 났지만 백준에서는 통과됐다.)

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

public class Main {
    static int[] dp; //중복 계산을 막기 위해 중간 결과값들을 저장하기 위한 배열이다.

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

        int N = Integer.parseInt(br.readLine());
        dp = new int[N+1];

        dp[0]=1;
        dp[1]=1;
        /*
        //공간을 1000001 이 아니라 입력받은 N+1 공간을 생성하므로,
        //N=1 이 대입됐을 시, 배열 공간이 0,1 밖에 없으므로 2가 저장될 수가 없다.
        dp[2]=2;
         */
        System.out.println(solve(N));
    }

    //Top-down 방식
    private static int solve(int N) {
        if(dp[N]>=1)
            return dp[N];

        dp[N] = (solve(N-1) + solve(N-2))%15746;
        return dp[N];
    }
}

 

---

 

2번

→ Bottom-up 방식

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

public class Main {
    static int[] dp; //중복 계산을 막기 위해 중간 결과값들을 저장하기 위한 배열이다.

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

        int N = Integer.parseInt(br.readLine());
        dp = new int[N+1];

        dp[0]=1;
        dp[1]=1;
        /*
        //공간을 1000001 이 아니라 입력받은 N+1 공간을 생성하므로,
        //N=1 이 대입됐을 시, 배열 공간이 0,1 밖에 없으므로 2가 저장될 수가 없다.
        dp[2]=2;
         */
        System.out.println(solve2(N));
    }


    //Bottom-up 방식
    private static int solve2(int N){
        for(int i=2;i<=N;++i){
            dp[i] = (dp[i-1] + dp[i-2]) % 15746;
        }

        return dp[N];
    }
}

 

---

 

3번

→ Bottom-up 방식(메모제이션 x)

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

public class Main {
//    static int[] dp; //중복 계산을 막기 위해 중간 결과값들을 저장하기 위한 배열이다.

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

        int N = Integer.parseInt(br.readLine());

        /*
        dp = new int[N+1];

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

        //공간을 1000001 이 아니라 입력받은 N+1 공간을 생성하므로,
        //N=1 이 대입됐을 시, 배열 공간이 0,1 밖에 없으므로 2가 저장될 수가 없다.
        dp[2]=2;
         */
        System.out.println(solve3(N));
    }

    //Bottom-up 방식 (메모제이션 없이 사용하는 방식)
    private static int solve3(int N){
        if(N==1)
            return 1;
        if(N==2)
            return 2;

        int sum = 0;
        int val1 = 1;
        int val2 = 2;

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

        return sum;
    }
}