[백준] 알고리즘 3-1일차 다이나믹 프로그래밍

1. 11726번 : 2 x n 타일링 문제

11726번: 2×n 타일링

2xn 타일링 문제는 큰 문제에서 작은문제로 어떻게 만들것인가가 중요한데, 오른쪽 끝에 타일을 붙여서 모양을 만든다고 생각하면 가로가 1인경우와 2인경우로 나눌 수 있다.

즉 오른쪽에 가로가 1인 타일을 붙이면 총 가로가 N일때, 남은 부분은 N-1의 크기가된다. 마찬가지로 2로 N-2가 된다.

 

점화식을 주석에 있는 것처럼 세워준후 문제를 해결한다.

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1001];
// 점화식 : dp[N] = dp[N-1] + dp[N-2] 
// 큰 문제 = 작은 문제로 나눠서 큰문제를 해결한다.
// 큰 문제 n은 가로의 길이가 n-1 + 1 인 경우와 n-2 + 2 인 부분으로 나눌 수 있다.
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    dp[1] = 1, dp[2] = 2, dp[3] = 3;
    for (int i = 4; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
    }
    cout << dp[n];
}

 

2. 11727번 : 2 x n (2) 타일링 문제

11727번: 2×n 타일링 2

위에 문제와 비슷하지만, 2x2 타일이 하나 추가된점이다. 마찬가지로 점화식을 유추해서 문제를 쉽게 해결할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[1001];
// 점화식 : dp[N] = dp[N-1] + dp[N-2]*2 
// 큰 문제 = 작은 문제로 나눠서 큰문제를 해결한다.
// 큰 문제 n은 가로의 길이가 n-1 + 1 인 경우와 n-2 + 2 경우와 n-2 + 2 인경우 총 3가지가 있다.
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    dp[1] = 1, dp[2] = 3;
    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + (dp[i - 2]*2))%10007;
    }
    cout << dp[n];
}

3. 9095번 : 1,2,3 더하기

9095번: 1, 2, 3 더하기

점화식을 세워보면 끝자리에 1 2 3 이 오는 경우를 먼저 생각해본다.

1. 끝자리에 1이오는경우 이전까지의 결과물은 N-1이 될 것이다.

2. 마찬가지로 2는 N-2

3. 3도 N-3이 될 것이다.

 

DP[N] = DP[N-1]+DP[N-2]+DP[N-3] 의 점화식을 도출해낼 수 있다.

DP[0]을 지정해두면 문제를 쉽게 해결할 수 있는데, 이 말은 즉슨 DP는 n을 1, 2, 3의 합으로 나타내는 방법의 수

즉 수를 한개도 사용하지 않는 경우의 수 1가지가 있다고 볼 수 있습니다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[11];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    dp[0] = 1, dp[1] = 1, dp[2] = 2, dp[3] = 4;
    for (int i = 4; i < 11; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    while (T--) {
        int n;
        cin >> n;
        cout << dp[n] << "\n";
    }
}

4. 11052번 : 카드 구매하기

11052번: 카드 구매하기

DP[N] = N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값

점화식의 의미를 설정하였으면, 점화식을 세워야하는데 순차적으로 생각을 해봅시다.

1개의 카드를 구매한다 -> price[1] 째에 있는 경우의 수 밖에 되지않습니다. 즉 마지막에 오는 카드가 1장이라는 뜻입니다. N-1 + 1 이 되겠습니다.

2개의 카드를 구매한다 -> 마지막에 오는 카드가 2장이라는 뜻으로 N-2 + 2로 둘 수 있습니다.

 

즉 이런식으로 쭉해서 지불해야하는 금액의 최댓값을 구하는 것이므로 i번째 금액의 최댓값은 1~i까지의 가격대를 모두 검사해봐야 합니다.

DP[i] = DP[i-j] + price[j]

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[1001]; // N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값
int price[1001];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> price[i];
    }
    dp[1] = price[1];
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            int temp = dp[i - j] + price[j];
            dp[i] = max(temp, dp[i]);
        }
    }
    cout << dp[n];
}

5. 16194번 : 카드 구매하기(2)

16194번: 카드 구매하기 2

카드 구매하기(1)과 같은문제이다.

다만 최솟값을 구해야하므로 이전의 코드에서 초기값을 설정해줘야 최솟값을 구할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[1001]; // N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값
int price[1001];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> price[i];
    }
    dp[1] = price[1];
    for (int i = 2; i <= n; i++) {
        dp[i] = price[i];
        for (int j = 1; j <= i; j++) {
            int temp = dp[i - j] + price[j];
            dp[i] = min(temp, dp[i]);
        }
    }
    cout << dp[n];
}