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

1. 1699번 : 제곱수의 합

1699번: 제곱수의 합

DP[N] = 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 저장

N이 되기위해 제곱수들의 합으로 표현할 때 가장 마지막에 오는 숫자가 중요하다.

가장 마지막에 오는 숫자를 j라고 한다면 1부터 N까지 j*j를 계속해서 반복해서 경우의 수를 살펴볼 것이다.

그렇다면 dp[i] = dp[i-j*j]+1 이라는 식을 도출해낼 수 있다.

마지막의 제곱수에서 N을 뺀다면 현재의 제곱수 이전의 값은 최소개수를 이미 저장하고 있기 때문에 현재의 제곱수를 포함시켜 +1한 것과 1~N까지 j*j를 돌려 계산한 것들 중 가장 최소의 값을 저장하여 출력하는게 이 문제의 포인트이다.

문제는 1,2,3 더하기와 비슷하다.

#include <iostream>
#include <algorithm>
using namespace std;
int dp[100001];
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++) {
        dp[i] = i;
        for (int j = 1; j * j <= i;j++) {
            if (i == j) dp[i] = 1;
            else {
                dp[i] = min(dp[i - j * j]+1, dp[i]);
            }
        }
    }
    cout << dp[n];
}

2. 2225번 : 합분해

2225번: 합분해

dp[i][j] = k개를 이용하여 n을 만들 수 있는 경우의 수를 저장한다.

마지막 자리에 어떤수가 올지 모르니 변수를 하나 만든다고 생각하면 된다.

n을 만들려고 마지막 자리에 무엇이 올 수 있을지 결정해주는 변수 한개를 더 두게된다면 l

0~n까지의 l을 마지막에 붙인다면 전체 i개중 마지막 개수한개를 뺀 i-1개의 요소들과 마지막에 붙은 l요소를 이용하여 경우의 수를 구해준다.

#include <iostream>
#include <algorithm>
using namespace std;
int dp[201][201]; // k개를 이용하여 n을 만들 수 있는 경우의 수
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,k;
    cin >> n >> k;
    for (int i = 0; i <= n; i++) {
        dp[1][i] = 1;
    }
    for (int i = 2; i <= k; i++) {
        for (int j = 0; j <= n; j++) {
            for (int l = 0; l <= j; l++) {
                dp[i][j] += dp[i - 1][l]; 
                dp[i][j] %= 1000000000; 
            }
        }
    }
    cout << dp[k][n];
}

3. 14501번 : 퇴사

14501번: 퇴사

n의 수가 작으니 브루트포스로도 해결이 가능하다.

1. 상담을 한다.

2. 상담을 안한다.

두종류로 재귀함수를 돌려서 문제를 해결할 수 있다.

시간복잡도는 O(N^2)으로 다이나믹으로 해결한다면 O(N)으로 해결할 수 있다.

이 부분은 추후에 업데이트하도록 하겠다. 메모이제이션 부분을 다시 공부중이라 아직 숙지를 하지못했다.

#include <iostream>
using namespace std;
int n, ans = 0;
int t[16], p[16];
void go(int day, int sum) {
    if (day > n + 1) return;
    if (day == n + 1) {
        ans = max(sum, ans);
        return;
    }
    go(day + 1, sum);
    go(day + t[day], sum + p[day]);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> p[i];
    }
    go(1, 0);
    cout << ans;
}