Backjoon(백준) 1904번 - 01타일(Java)

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

 

풀이 전략

 식을 구해보고 규칙을 찾은 뒤 점화식을 도출한다. (규칙은 맨뒤에 적어놨습니다)

 하위 식에서 상위 식을 구하는 bottom-up 방식을 통해. 결과 값을 더해가면서 최종 답을 구한다.

 

 핵심은 문제를 잘 이해해서 규칙을 찾는 것이다.

소스 코드

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

// 1904번 01타일
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        long dp1 = 1;
        long dp2 = 2;
        long result = 3;
        if (n == 1)
            result = 1;
        else if (n == 2) {
            result = 2;
        } 
        else if (n > 2) {
            for (int i = 3; i <= n; i++) {
            result = (dp1 + dp2) % 15746;
            dp1 = dp2;
            dp2 = result;
            }
          }
       
        bw.write(result + "\n");
        
        bw.flush();
        br.close();
        bw.close();

    }

}

 * 규칙 

1번째 1 

2번째 11 00

3번째 100 (+00) 111 (+1) 001 (+1)

4번째 1100 (+00) 0000 (+00) 1001 (+1) 1111 (+1) 0011 (+1)

 

이런식으로 크기 1부터 4까지 구해보면 n번 크기의 타일은 n - 2 번째의 타일에 '00'을 붙이고 (붙이는 것은 오른쪽에서)  n - 1 번째 타일에 '1'을 붙인 결과의 합과 같다.

 

따라서 n[i] = n[i - 2] + n[i - 1]라는 점화식을 도출할 수 있다.

 

도출된 결론을 bottom-up 방식(하위 계산들로 최종 결과값을 도출하는 방식)으로 값을 구한 후 출력한다.