[백준/BOJ] 1904번 : 01타일 (Java)

문제요약

00과 1로 만들 수 있는 2진 수열의 개수를 구하시오.

 

풀이

N=1일 때, [1] - 1개

N=2일 때, [00, 11] - 2개

N=3일 때, [001, 100, 111] - 3개

N=4일 때, [0000, 0011, 1001, 1100, 1111] - 5개

N=5일 때, [00001, 00100, 10000, 00111, 10011, 11001, 11100, 11111] - 8개

 

즉, N[i] = N[i-1] + N[i-2]

피보나치 수열로 풀 수 있다.

 

코드

import java.util.Scanner;

public class BOJ_1904 {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] tiles = new int[n+1];
		tiles[1] = 1;
		tiles[2] = 2;
		
		for (int i=3; i<=n; i++) {
			tiles[i] = (tiles[i-1] % 15746) + (tiles[i-2] % 15746);
		}
		
		System.out.println(tiles[n] % 15746);
		scan.close();
	}

}

 

+200920 추가

다시 풀어보니 계속 런타임 에러가 떠서 무슨 일인가 했더니

n이 0인 경우 배열 할당에 문제가 생겨서 그랬다.

import java.io.*;

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

        if (n <= 2) {
            System.out.println(n);
        } else {
            int[] tiles = new int[n+1];
            tiles[1] = 1;
            tiles[2] = 2;

            for (int i = 3; i <= n; i++) {
                tiles[i] = (tiles[i - 1] + tiles[i - 2]) % 15746;
            }

            System.out.println(tiles[n]);
        }
    }
}

 

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