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

문제

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

00 또는 1을 총 n개 붙여서 만들 수 있는 이진수열의 개수를 구하는 문제

풀이

n을 1부터 5까지 늘려가며 어떤 수열이 만들어질 수 있는지 구해보면 규칙을 찾을 수 있다.

n번째에 만들 수 있는 이진 수열의 개수 = (n-1번째에 만들 수 있는 이진 수열 개수) + (n-2번째에 만들 수 있는 이진 수열 개수)

 

이 규칙의 원리는 n-1번째에 만들어진 이진 수열의 맨 뒤에 '1'을 붙인 값들 + n-2번째에 만들어진 이진 수열의 맨 뒤에 '00'을 붙인 값들

이 두 가지가 합쳐져서 n번째의 이진 수열이 만들어진다는 점을 고려하면 쉽게 찾을 수 있다.

 

오답노트

문제에서 답을 출력할 때 숫자를 15746으로 나눈 나머지를 출력하라고 해서 최종 값에 나머지 연산을 해줬는데 틀렸다.

//오답
System.out.println(d[n]%15746);

 

이유는 이 점화식이 피보나치 수열과 동일한 형태인데, n이 조금만 커져도 결과값이 기하급수적으로 커지는 특징이 있다.

그런데 dp배열은 long크기까지만 저장 가능하므로 dp배열에 피보나치수를 저장할 때마다 비트가 잘려서 저장되는 일이 발생한 것.

(이번주 컴시에서 열심히 공부한 어셈블리 복사 명령어가 생각난다... 큰 타입에서 작은 타입으로 복사할 때는 비트가 잘려서 저장된다 ㅎ)

그래서 마지막에 나눠주는 게 아니라 dp에 저장할 때마다 모듈러 연산을 수행해야 한다.

//정답
d[i] = (d[i-1] + d[i-2])%15746;

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] d = new long[1000001];
        d[1] = 1;
        d[2] = 2;
        for(int i=3; i<=1000000; i++){
            d[i] = (d[i-1] + d[i-2])%15746;
        }
        System.out.println(d[n]);
    }
}