[백준] 동적 프로그래밍 - 1904번 01타일 (Java)

문제링크

1904번: 01타일

 

접근한 방법

• 동적 프로그래밍

---

풀이 방법

일단, 규칙을 찾는 데 집중하여 아래 표와 같이 그려보며 규칙을 발견하였다.

N-1자리 끝에는 1을 붙이고,

N-2자리 끝에는 00을 붙여서 N자리 수를 만들 수 있다.

 

$a_{n} = a_{n-1} + a_{n-2}$

 

$a_{n}$	나열	개수
$a_{1}$	1	1
$a_{2}$	11 00	2
$a_{3}$	111 001 100	3
$a_{n}$	1100 0000 1111 0011 1001	5

 

---

소스코드 작성 방법

• a배열의 크기를 n+1로 지정
• a[2]를 초기화하면 n=1일 경우 런타임 에러가 발생하므로, a[0]을 초기화한다.

 

실수한 점

• 반복문 안에서 %15746을 해주지 않고, 최종값에 %15746을 해주었던 점

 

소스코드

package baekjoon.dp;
import java.io.*;

public class Q_1904_01Tile {
    public static int solution(int n) {
        int[] a = new int[n+1];

        a[0] = 1; a[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            a[i] = (a[i - 1] + a[i - 2])%15746;
        }
        return a[n];
    }

    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());
        bw.write(solution(n)+"\n");

        br.close();
        bw.close();
    }
}