[백준 알고리즘] 1904번 01타일(Java) 문제 풀이

문제

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

1904번: 01타일

문제에 대한 이해

문제가 길다고 당황하지 말고 결국에는 DP문제이다.

어떻게 풀 것인가?

위와같이 문제에서 DP라는 생각이 들어서 DP접근을 하여 문제를 풀었다.

타일이 1개일 경우 만들어지는 경우의 수는 1개

타일이 2개일 경우 만들어지는 경우의 수는 2개

타일이 3개일 경우 만들어지는 경우의 수는 3개였다.

타일이 4개일 경우 만들어지는 경우의 수는 5개였다.

 

위 와같은 방식으로 점화식은 d(n+2) = d(n+1) + d(n) (n > 2, n = 2, n = 1) 이다.

간단했다.

시간복잡도

DP를 이용했다면 O(N)이였을 것 이다.

공간복잡도

나는 단순 계산 방식으로 DP를 구현했기에 O(1)이다.

풀면서 놓쳤던점

없음

이 문제를 통해 얻어갈 것

간단한 DP 문제

내 코드 

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

// 백준알고리즘 1904번 01타일
public class Main {
    static int N;

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

        System.out.println(Tile(N));

    }

    public static int Tile(int a) {

        if (a == 1) {
            return 1;
        }

        if (a == 2) {
            return 2;
        }

        // 초기 값
        int val1 = 1;
        int val2 = 2;
        int sum = 0;

        for (int i = 2; i < a; i++) {
            sum = (val2 + val1) % 15746;    // 이전 값과 이전의 이전 값의 합
            val1 = val2;    // 이전의 이전 값은 이전 값으로 변경
            val2 = sum;        // 이전 값은 현재 합 값으로 변경
        }

        return sum;

    }
}