[백준/C언어] 1904번 - 01타일

백준 웹사이트 "1904번 - 01타일" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

1904번: 01타일

---

소스 코드

#include <stdio.h>

int main(void){
    int N;
    scanf("%d", &N);

    //visual studio에서는 스택 사이즈 때문에 큰 수에서 에러
    int num[N]; //num[N-1] -> 길이가 N인 수열의 개수
    num[0] = 1;
    if(N>1){
        num[1] = 2;
        for(int i=2; i<N; i++){
            num[i] = (num[i-2] + num[i-1])%15746;   //마지막에 나머지를 구하면 overflow
        }
    }

    printf("%d\n", num[N-1]);
}

---

문제 풀이

  코딩을 시작하기 전에 가장 먼저 해야할 것은 바로 점화식을 구하는 것입니다. 길이가 1인 2진 수열의 개수, 길이가 2인 2진 수열의 개수를 토대로 길이가 3, 4, 5, ... , N인 2진 수열의 개수를 차근차근 구해야 하기 때문이죠.

  길이가 n인 2진 수열의 개수를 num[n]이라고 합시다. 길이가 n인 모든 2진 수열은 두 카테고리 중 하나로 나뉩니다. '마지막 타일이 1인 2진 수열' 또는 '마지막 타일이 0인 2진 수열'이죠. 각각의 개수가 어떻게 될까요? 마지막 타일이 1이면 마지막 타일을 제외한 n-1개의 타일에 대해서는 어떠한 제약도 없으므로 그 개수는 num[n-1]입니다. 마지막 타일이 0일 때는 반드시 마지막에서 두번째 타일도 0이므로, 가능한 수열의 개수는 num[n-2]입니다. 따라서 num[n] = num[n-1] + num[n-2]라는 관계식이 성립하게 됩니다.

 

num[0], num[1]만 구한다면 이후 num[3], num[4], ... , num[n]은 앞선 값들을 토대로 구할 수 있습니다.

  하지만 이 점화식 그대로 문제를 풀면, overflow에 의한 에러가 뜹니다. n이 충분히 커진다면 num의 값이 int의 범위를 넘기 시작하죠. 따라서 마지막 출력 직전에 15746으로 나누지 말고, num에 값을 저장할 때마다 15746으로 나누어야 합니다. 합의 나머지는 나머지의 합과 같으므로 정답이 변할 일은 없습니다.