BOJ 1700 멀티탭 스케줄링 / BOJ 14501 퇴사 / BOJ 11052 카드 구매하기 (그리디, DP)

백준 BOJ 1700번 : 멀티탭 스케줄링

난이도 : Gold I

카테고리 : 그리디

 

멀티탭 구멍의 수와 전자제품의 총 사용횟수가 주어지며, 사용되는 전자제품의 순서가 주어질 때 멀티탭에서 플러그를 빼는 최소 횟수를 구하는 문제입니다.

 

다음의 우선 순위에 따라 처리해주면 됩니다.

(1) 이번에 사용할 전자제품이 이미 꽂혀있는 경우 : 이 경우는 아무런 변화를 주지 않고 그냥 넘어가면 됩니다.

(2) 콘센트가 한 칸이라도 비어있는 경우 : 비어있는 구멍의 번호를 찾아서, 해당 번호에 현재 사용할 전자제품의 번호를 저장해주면 됩니다.

(3) (1), (2)가 모두 아닌 경우 현재 콘센트에 연결된 전자제품들 중에서 가장 마지막에 사용될 전자제품의 플러그를 제거해주면 됩니다.

앞으로 남은 order들 중에서 아래 코드의 last 변수가 가장 큰 것의 번호에 해당하는 전자제품을 제거해주면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, K; cin >> N >> K;

    vector<int> order(K);
    for(int i=0; i<K; i++) cin >> order[i];

    int ans = 0;
    vector<int> now(N);

    for(int i=0; i<K; i++) {
        bool check = false; // 이번에 사용할 전자제품이 이미 꽂혀있는 경우
        for(int j=0; j<N; j++)
            if(now[j] == order[i]) check = true;
        if(check) continue;

        for(int j=0; j<N; j++) // 콘센트가 한 칸이라도 비어있는 경우
            if(now[j] == 0) {
                now[j] = order[i];
                check = true;
                break;
            }
        if(check) continue;

        int lastMax = -1, change; // 가장 마지막에 사용될 전자제품의 플러그를 제거
        for(int j=0; j<N; j++) {
            int last = 0;
            for(int k=i+1; k<K; k++) {
                if(now[j] == order[k]) break;
                last++;
            }

            if(last > lastMax) {
                change = j;
                lastMax = last;
            }
        }
        now[change] = order[i];
        ans++;
    }

    cout << ans;
}

 

 

백준 BOJ 14501번 : 퇴사

난이도 : Silver III

알고리즘 카테고리 : DP

 

N개의 날짜동안 특정 길이의 날짜동안 지속되는 상담을 할 수 있고 그 때 받는 보상이 주어질 때, 최대로 받을 수 있는 보상을 구하는 문제입니다.

(특정 상담이 지속되는 동안에는 다른 상담을 할 수가 없고, 어떤 상담이 N일 이후까지도 지속된다면 그 상담은 할 수 없습니다.)

 

dp[i]를 i일 포함 그 이후로 받을 수 있는 최대 보상이라고 정의하고, dp[N-1]부터 재귀적으로 dp[0]까지 계산해오면서 dp[0]을 출력해주면 됩니다.

 

이제 점화식을 찾아봅시다.

다음과 같이 간단하게 점화식을 세울 수 있습니다.

 

dp[i] = max(dp[i], dp[i + 상담(i일)의 기간] + (상담(i일)의 보상))

 

 

이제 세운 점화식으로 아래와 같이 재귀적으로 dp를 탐색하는 구현만 수행해주면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

struct Consult { int time, value; };
vector<Consult> consult;

int N;
vector<int> dp; // dp[i] : "max value" can get after day "i"

int calc_dp(int day) {
    if(day >= N) return 0;
    if(dp[day] != -1) return dp[day];

    dp[day] = 0;

    if(day + consult[day].time <= N)
        dp[day] = max(dp[day], calc_dp(day + consult[day].time) + consult[day].value);

    return dp[day] = max(dp[day], calc_dp(day+1));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N;

    consult.resize(N);
    dp.resize(N, -1);

    for(int i=0; i<N; i++)
        cin >> consult[i].time >> consult[i].value;

    cout << calc_dp(0);
}

 

 

백준 BOJ 11052번 : 카드 구매하기

난이도 : Silver I

알고리즘 카테고리 : DP

 

card[1], card[2], ... , card[N]의 값이 주어질 때 card[i]의 i 값들을 적절히 합하여 N이 되는 card들의 합이 최대가 되도록 할 때 그 최댓값을 구하는 문제입니다.

 

dp[i]를 카드 i개를 갖기 위해 지불해야하는 금액의 최댓값으로 정의합시다. (문제에서 주어진 그대로)

 

점화식을 세워보면 다음과 같습니다.

 

dp[i] = max(dp[i-1] + card[1], dp[i-2] + card[2], ... , dp[0] + card[i])

(단, dp[0] = 0)

 

 

이제 위에서 세운 점화식으로 문제를 풀어주면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> card(N+1), dp(N+1); // dp[i] : max cost of buying "i" cards
    for(int i=1; i<=N; i++) cin >> card[i];

    dp[1] = card[1];

    for(int i=2; i<=N; i++)
        for(int j=1; j<=i; j++)
            dp[i] = max(dp[i], dp[i-j] + card[j]);

    cout << dp[N];
}