[백준/C++] 꺾이지 않는 마음 1 (No. 26142)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 처음 봤을 때 활을 쏠 용이 정해지면 그 용을 다시 쏠 필요는 없겠다는 생각이 들었다.

 

왜냐하면 하루에 하나의 활만 쏠 수 있기 때문에 a일에 용을 쏘고 a+b일에 용을 다시 쏜다면 애초에 a+b일에 용을 쏘면 되기 때문이다.

 

이를 바탕으로 활을 맞출 용이 정해진다면 그 용들 중 성장하는 키의 수치가 가장 큰 용을 나중에 맞추면 최대값을 얻는다는 것을 알 수 있다.

 

문제는 활을 맞출 용을 정하는 방법이다.

D[i]와 H[i]값이 있기 때문에 단순히 그리디하게 K일에 어떤 용들을 맞출지 정하기가 어렵다.

 

다행히 N의 값이 10000으로 작기 때문에 DP를 활용한다면 i번째 용을 포함할지 말지를 이용해 문제를 해결할 수 있다.

 

이전에 쏠 용들이 정해진다면 D[i]값이 높은 용을 늦게 맞추면 최대값을 얻는다는 사실을 알았다.

 

이를 이용하면 D[i]를 기준으로 정렬해 D[i]값이 높은 용을 무조건 마지막일에 쏠 수 있다.

 

그리고 DP를 DP[i][k] = i번째 용까지 포함한 경우 k일에 얻을 수 있는 최대값으로 정의한다.

 

그러면 아래와 같은 그림을 얻을 수 있다.

fig1

 

빨간색 칸에 있는 값을 얻기 위해서는 어떻게 해야할까?

 

빨간색 칸은 DP[3][2]로 3번째 용까지 포함한 경우 2일차의 최대 값이다.

 

먼저 초록칸인 DP[2][1]의 값을 생각하면 2번째 용까지 포함한 경우 1일차의 최대값이다.

즉, 한마리의 용이 선택된 상태다.

 

그러면 이를 이용해 3번째 용을 무조건 포함해 2마리를 선택한 경우를 아래와 같이 만들 수 있다.

 

DP[2][1]+H[3]+D[3]*1

여기서 H[3]은 초기값이므로 당연히 더하는 값이고 1은 마지막에 이 용을 쐈기 때문에 1을 곱한 것이다.

 

이때 왜 마지막에 쏜다고 가정하냐면, 우리는 D[i]값을 기준으로 오름차순으로 정렬했기 때문에 나중에 나오는 용을 마지막에 쏘는게 이득이기 때문이다.

 

이제 3번째용을 무조건 포함한 값을 구했으므로, 3번째 용을 포함하지 않고 구했던 최댓값과 비교하면 된다.

초록색 칸의 DP[2][2]가 3번째 용을 포함하지 않고 구한 최대값이므로

DP[3][2] = max(DP[2][2], DP[2][1]+H[3]+D[3]*1)

로 DP값을 구할 수 있다.

 

+ 다른 사람의 경우 더 효율적으로 푼 풀이가 있었다.

2차원 DP를 1차원으로 압축해 푸는 방법인데, DP[k] = k일에 용을 쏴서 얻은 최대값으로 정의한다.

이후 i번째 용을 포함하도록 DP에 바로 저장하면 된다.

 

그러면 DP[k] = max(DP[k], DP[k-1] + H[i] + D[i] * (k-1)) 로 문제를 해결할 수 있다.

(이때 k는 일, i는 용의 번호)

그리고 한번 맞춘 용이 중복되지 않도록 N-1에서 1 순서로 갱신해 나가야한다.

 

 

 

[아이디어 정리]

1. 한번 맞춘 용은 다시 맞출 필요가 없다. (왜냐하면 나중에 맞출 필요가 있다면, 애초에 나중에 맞추면 되기 때문)
2. 맞출 용이 정해지면 D[i]값을 기준으로 맞추는 순서가 정해지므로 D[i]를 기준으로 정렬한다.
3. DP를 이용해 i번째 용을 맞추는 경우와 i번째 용을 맞추지 않는 경우로 구분해 비교하고 max값을 갱신해 나간다.

 

 

Code1 (2차원 DP)

 

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    vector<pair<long long,long long>> D(N);
    for (int i=0; i<N; i++)
    {
        cin >> D[i].first >> D[i].second;
        // first = 증가, second는 초기 값
    }
    vector<long long> ans(N);
    // 오름차순 정렬
    sort(D.begin(), D.end(), [](pair<long long,long long>a, pair<long long,long long>b) {
        return a.first == b.first ? a.second < b.second:a.first < b.first;
    });
    long long hap=0;
    vector<vector<long long>> DP(N, vector<long long>(N,0));
    //i,k
    DP[0][0] = D[0].second;
    for (int i=1; i<N; i++)
    {
        DP[i][0] = max(DP[i - 1][0], D[i].second);
    }

    for (int i = 1; i < N; i++)
    {
        for (int j=i; j<N; j++)
        {
            DP[j][i] = max(DP[j-1][i],DP[j - 1][i - 1] + D[j].second + D[j].first * i);
        }
    }

    for (int i = 0; i < N; i++) {
        cout << DP[N - 1][i] << "\n";
    }

    return 0;
}

 

 

 

Code1 (1차원 DP)

 

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    vector<pair<long long,long long>> D(N);
    for (int i=0; i<N; i++)
    {
        cin >> D[i].first >> D[i].second;
        // first = 증가, second는 초기 값
    }
    // 오름차순 정렬
    sort(D.begin(), D.end(), [](pair<long long,long long>a, pair<long long,long long>b) {
        return a.first == b.first ? a.second < b.second:a.first < b.first;
    });
    vector<long long> DP(N+1,0);
    //i,k    
    for (int i = 0; i < N; i++)
    {
        for (int j=N; j>=1; j--)
        {
            DP[j] = max(DP[j], DP[j - 1] + D[i].second + D[i].first * (j - 1));
        }
    }

    for (int i = 1; i <= N; i++) {
        cout << DP[i] << "\n";
    }

    return 0;
}

---

 

풀이를 생각하고 정렬해서 풀어야겠다는 생각은 했지만, 그리디하게 풀 수 있을거 같아서 계속 고민했다.

 

그런데 아무리 생각해도 보이지 않아서 어떻게 풀어야할까 고민했는데, i번째 용을 포함한 경우와 포함하지 않은 경우를 비교해 DP로 풀 수 있었다.

 

실력이 많이 퇴화한 거 같다...ㅠㅠ

 

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