[ 백준 1904 ] 01타일 (C++)

백준의 01타일(1904) 문제이다.

[ 문제 바로가기 ]

[ 문제를 다시 푸는 과정에서 이 글에 대한 풀이글을 재포스팅 하였습니다.

  아래의 글을 읽으셔도 문제를 푸는 데는 무관하지만, 더욱 구체적인 설명을 원하시는 분들께서는

  아래의 링크를 이용해 주시면 감사하겠습니다.

  [ 백준 01타일(1904) 풀이 새로운 포스팅 ]

]

[ 문제풀이 ]

1) 먼저, 본인은 각 자리수별로 만들 수 있는 이진수의 갯수를 저장할 DP[] 1차원 배열을 사용하였다.

   DP[a] = b 의 의미는 "길이가 a인 이진수의 갯수는 b개입니다."를 의미한다.

   그렇다면, 초기식들을 한번 정리해보자.

   DP[0] 은 얼마일까??? 길이가 0인 이진수의 갯수는 0개이다. 따라서 DP[0] = 0

   DP[1]은 얼마일까?? 길이가 1인 이진수의 갯수는 1개이다. 왜냐하면, 00은 2개가 한 세트이기 때문에, 0이 단독적으로 하나만은

   올 수 없기 때문에 한 자리 숫자로 나타낼 수 있는 이진수는 '1' 1개이다. DP[1] = 1

   DP[2]는 얼마일까? 2개일 것이다. '00', '11' 로 2개가 되므로 DP[2] = 2가 될 것이다.

   DP[3]은 얼마일까?? 아마, '001', '100', '111' 로 3개가 될 것이다.

   여기서 점화식을 도출해내보자 ! DP[N] = DP[N-1] + DP[N-2] 가 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MODULER 15746
#define MAX 1000000 + 1
using namespace std;
 
int N;
int DP[MAX];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    DP[0] = 0;
    DP[1] = 1;
    DP[2] = 2;
 
    for (int i = 3; i <= N; i++)
    {
        DP[i] = DP[i - 1] + DP[i - 2];
        DP[i] = DP[i] % MODULER;
    }
    cout << DP[N] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}