1904번: 01타일(백준 C++)

1904번: 01타일 링크

코드

#include <iostream>
using namespace std;

void solve(int n){
    int num1 = 1, num2 = 2, num3;
    if(n <= 2) cout << n << endl;
    else{
        for(int i=3; i<=n; i++){
            num3 = num1 + num2;
            num3 %= 15746;
            num1 = num2;
            num2 = num3;
        }
        cout << num3 << endl;;
    }
}
int main() {
    int n;
    cin >> n;
    solve(n);

    return 0;
}

풀이 및 사견

문제

미쳐버린 동주가 쏘아올린 작은 문제이다.
지원이 아버지가 지원이 공부하라고 '0' 타일과 헉 뭐지 '0' 귀엽게 생겼다.

이것 보세요 귀엽지 않나요?

아무튼 '0' 타일과 '1' 타일을 줬는데 그걸 동주가 '0' 타일끼리 붙여버렸다.
'0' 단일 타일이 있었는데요, 없었습니다...

그래서 아무튼 '1' 타일과 '00' 타일로 2진수열을 만들어야 하는 문제이다.

---

다이나믹 프로그래밍 문제니까, 일단 점화식을 한 번 알아내어 보자.

N = 1

1

N = 2

00
11

N = 3

111
001
100

N = 4

1111
0011
1100
1001
0000

N = 5

11111
00111
10011
11001
11100
00001
00100
10000

1 -> 2 -> 3 -> 5 -> 8

즉, N = N-1 + N-2 이다.

이에 맞춰서 함수를 작성해 주면

void solve(int n){
    int num1 = 1, num2 = 2, num3;
    if(n <= 2) cout << n << endl;
    else{
        for(int i=3; i<=n; i++){
            num3 = num1 + num2;
            num3 %= 15746;
            num1 = num2;
            num2 = num3;
        }
        cout << num3 << endl;;
    }
}

이렇게 작성이 되는데, 주의할 점이 있다.
바로 나온 결과값에 15746을 나눈 나머지를 출력해야 한다는 것이다.

Q. 그냥 끝가지 다 더하고 마지막에 나눠주면 안되나요?

안됩니다.
N이 최대 1000000의 자연수이기 때문에 중간에 나눠주지 않으면 끝도없이 커져 오버플로우가 발생하여
올바른 값을 도출할 수 없게 됩니다. 그렇기 때문에, 반복문이 1회 돌 때마다 나눠주면 올바른 값을 구할 수 있습니다.

이 점을 유의해서 문제를 풀면 풀 수 있는 DP 문제였다.