백준 1904 - 01타일 (c++)

백준 1904 - 01타일

문제 링크

생각 및 접근

• 문제가 구구절절 길었지만, 결국엔 00과 1을 조합해서 n의 길이를 만들었을 때, 몇 개의 숫자를 만들 수 있는지 계산하는 문제였다.
• dp[i]
  • 00과 1을 조합해서 i의 길이를 만들었을 때, 몇 개의 숫자를 만들 수 있는지 저장
  • 이전 값에서 00을 붙여서 길이가 i인 숫자를 만들 수 있는 경우 : dp[i - 2]
  • 이전 값에서 1을 붙여서 길이가 i인 숫자를 만들 수 있는 경우 : dp[i - 1]
  • ∴ dp[i] = dp[i - 2] + dp[i - 1]

코드

#include <bits/stdc++.h>
using namespace std;

int dp[1000001], n;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin >> n;

    dp[1] = 1;  dp[2] = 2;

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

    cout << dp[n];
}

채점 결과