01백준 1904번 - 01타일문제 C++ [다이나믹 프로그래밍 알고리즘]

📍 백준 1904번 - 01타일문제 C++ [다이나믹 프로그래밍 알고리즘]

---

🧩문제 요약

<다이나믹 프로그래밍 알고리즘>

1, 00인 타일이 있다고 할 때, 

n이 주어지면 n개의 타일을 이용해 만들 수 있는 모든 가짓수를 구하라. 

대신 %15746의 나머지를 return 할것. 

---

🧾내가 작성한 초기 코드 

#include <iostream>
using namespace std; 

int arr[1000001];

int solve(int n ){
    if(n==1){
        return 1; 
    }
    if(n==2){
        return 2; 
    }
    if(arr[n] != 0){
        return arr[n];
    }
    else{
        arr[n] = solve(n-1) + solve(n-2);
        return arr[n];
    }

}

int main(){
    int n ;
    cin >> n ;
    cout << solve(n)%15746 << "\n";
}

---

👍이 문제에서 배운점

처음에 재귀로 호출할 때 어떤 연관이 있는지 찾아내기 힘들었다. 

그런데 결국 n이 주저였을 때 n으로 만들 수 있는 타일은 1  + (n-1), 00 + (n-2)라는 규칙을 찾았다. 

하지만 자꾸 정답이 아니어서 뭐가 문제인지 조금 헤맸다. 

😕 문제점 1. 

long long타입으로도 커버되지 않는 큰 숫자. 

✅ %15746

이 문제는 재귀함수를 만들고 DP로 풀이를 진행하는 것이 중요한 문제이지만 타입도 고려를 해봐야 한다.

재귀 함수를 작성하다 보면 피보나치 수열을 따른 다는 것을 알 수 있다.

n의 최대는 1000000이다. 그래서 피보나치 수열의 값이 매우 커질 수 있다. 이렇게 되면 long long타입으로도 감당할 수 없게 된다. 

 

그래서 문제에서는 %15746을 하여 값을 return 하게 하고 있는데 이것을 잘 이해하지 못해서 계속 틀린답이 나온것이였다. 

 

이는 최종 답을 모듈러 값으로 요구하는 것이고 경우의 수가 너무 크면 마지막에만 %연산을 해주는 것이 아니라 계산 과정에서도 계속 %해줘야 한다. 

안그러면 중간에 오버플로우가 발생하게 된다. 

 

---

🧾 완성된 코드 

#include <iostream>
using namespace std; 

int arr[1000001];

int solve(int n ){
    if(n==1){
        return 1; 
    }
    if(n==2){
        return 2; 
    }
    if(arr[n] != 0){
        return arr[n];
    }
    else{
        arr[n] = (solve(n-1) + solve(n-2))%15746;
        return arr[n];
    }

}

int main(){
    int n ;
    cin >> n ;
    cout << solve(n)%15746 << "\n";
}