[백준 1904번] 01타일 C++

www.acmicpc.net/problem/1904

1904번: 01타일

참나 다 풀어놓고 마지막에 처릴 잘 못 해서 엄청 시간쓴 문제;

DP로 푸는데 cnt 함수 변수로 타일의 남은 칸을 줬음

 

그리고 남은 칸들은 1로 구성된 1칸 or 00으로 구성된 2칸 순으로 채워올라가면서 

변수만큼의 칸을 다 채우는데 필요한 타일의 갯수를 구함

 

중요한건 cnt함수 내에서 메모이제이션값에 미리 %15746 처리를 했는데

변수 범위를 따지면 메모이제이션이 int 범위를 초과할 수 있고 이경우 틀림

(여기서 한참 헤맴)

 

조금.... dp에 다가서는느낌

 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[1000001];
 
int cnt(int x) {
    //기저사례
    if (x == 0) return 0;
    if (x == 1) return 1;
    if (x == 2) return 2;
 
    int& ret = dp[x];
    if (ret != -1) return ret % 15746;
 
    return ret = (cnt(x - 2) + cnt(x - 1)) % 15746;
}
int main() {
    int n;
    cin >> n;
    memset(dp, -1, sizeof(dp));
    cout << cnt(n);
 
    return 0;
}