[C++] 백준 26093번: 고양이 목에 리본 달기 - DP

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

26093번: 고양이 목에 리본 달기

---

 

양 옆에 위치한 고양이와 방울의 종류가 같지 않도록 함과 동시에 만족도를 최고로 높이는 방법을 찾아야한다.

그래서 접근한 방법은 단순히 이전 고양이의 가장 높은 만족도의 방울 번호와 다음으로 높은 만족도의 방울 번호를 저장하여 현재 순서의 고양이의 방울 번호와 비교하여 만족도의 합을 저장하는 방식이다.

 

쉽게 말해, 

1번 고양이의 만족도의 순서는 1, 2, 3번 방울이라고 하고,

2번 고양이의 만족도 순서 역시 1, 2, 3번 방울이라 한다면

2번 고양이까지 방울을 주었을 경우 가능한 만족도의 최대 합은

1번 고양이 1번 방울 + 2번 고양이 2번 방울 

혹은

1번 고양이 2번 방울 + 2번 고양이 1번 방울이다.

그러므로 방울들의 합을 dp 테이블에 저장하여 최대의 만족도를 구해주면 된다.

#include <iostream>
using namespace std;
int dp[101][10001];
pair<int,int>a[2], b[2];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> dp[i][j];
            if(i==1){
                if(arr[i][j]>a[0].first){
                    swap(a[0],a[1]);
                    a[0]={dp[i][j],j};
                }
                else if(dp[i][j]>a[1].first) a[1]={dp[i][j],j};
            }
        }
    }
    for(int i=2; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[0].second!=j) dp[i][j]+=dp[i-1][a[0].second];
            else dp[i][j]+=dp[i-1][a[1].second];
            if(b[0].first<arr[i][j]){
                swap(b[0],b[1]);
                b[0]={dp[i][j],j};
            }
            else if(b[1].first<dp[i][j]) b[1]={dp[i][j],j};
        }
        a[0]=b[0], a[1]=b[1];
        b[0]={0,0}, b[1]={0,0};
    }
    int ans=-1;
    for(int i=1; i<=m; i++) ans=max(ans, dp[n][i]);
    cout << ans;
}

 

위의 코드에서 a[0]은 이전 고양이의 가장 큰 만족도와 해당 번호를 저장하고,

a[1]은 이전 고양이의 다음으로 큰 만족도와 해당 번호를 저장한다.

 

b[0], b[1]은 각각 현재 고양이의 만족도와 번호를 저장하여

다음 고양이와 비교할 때 쓰인다.