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

문제

https://www.acmicpc.net/problem/1904

 

풀이 (총 소요 21m)

1. 시간초과 나는 재귀 풀이

: make 함수가 모든 가능한 타일 배열을 만드는 모든 경우를 확인하면서 진행. 즉, 재귀 방식으로 호출되는 모든 부분 문제를 반복적으로 해결하게 되면서 계산량이 매우 커지고 시간 초과가 발생하게 됨.

#include<iostream>
#include<algorithm>
#define endl "\n"
using namespace std;

int leng;
int num = 0;

void make(int length) {
    if (length == leng) {
        num++;
        num %= 15746;
        return;
    }

    else {
        if (length + 2 <= leng) make(length + 2);
        make(length + 1);
    }
}

void solution() {
    make(0);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> leng;

    // 로직
    solution();

    cout << num % 15746;

    return 0;

}

 

2. 맞은 dp 코드

: 동적 계획법을 이용하여 이전에 계산한 값을 저장하고, 이를 반복해서 재활용하는 방식으로 연산을 최적화. 이를 통해 동일한 연산을 여러 번 반복하지 않아 시간 복잡도를 크게 줄일 수 있음.

즉, C++에서는 배열이나 벡터를 사용해 이전 계산 결과를 저장하는 방식으로 구현되는 메모이제이션을 이용한 것.

#include<iostream>
#include<algorithm>
#define endl "\n"
using namespace std;

int leng;
int num = 0;
int dp[1000001];

void solution() {
    dp[0] = 0;
    dp[1] = 1; dp[2] = 2; dp[3] = 3;
    for (int i = 4; i <= leng; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> leng;

    // 로직
    solution();
    
	// 출력
    cout << dp[leng] % 15746;

    return 0;

}