[백준 2643번] 색종이 올려 놓기 (C++)

문제링크 : https://www.acmicpc.net/problem/2643

2643번: 색종이 올려 놓기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, result;
vector<pii>v;
int dp[101];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;

    for(int i=0; i<N; i++)
    {
        int x, y;
        cin >> x >> y;
        v.push_back({min(x,y), max(x,y)}); //앞에 작은 수로 배치
    }
    
    sort(v.begin(), v.end()); //정렬

    for(int i=0; i<N; i++)
    {
        dp[i]=1; //최소길이 1
        for(int j=0; j<i; j++)
        {
            if(v[i].first >= v[j].first && v[i].second >= v[j].second) //조건 1, 2 만족
            {
                dp[i] = max(dp[i], dp[j]+1); //길이 갱신
            }
        }
        result = max(result, dp[i]); //최대값
    }

    cout << result;

    return 0;
}

 

먼저 입력받은 쌍에 대해 정렬을 해주어야 한다.

원한 정렬을 위해 먼저 쌍의 앞에가 작은 값, 뒤가 큰 값이 오도록 벡터에 값을 넣어줬다.

정렬을 할 때 함수를 따로 정의하여 같이 정렬시켜도 되지만, 이 방법이 더 직관적으로 보여서 좋아보였다.

이후 벡터에 담긴 값들을 오름차순으로 정렬해준다.

 

이후에 반복문을 통해 문제에 주어진 조건에 맞게 dp를 갱신해준다.

우선 dp는 최소 길이가 1이므로 1로 초기화를 해준다.

이후 현재 위치 (i) 와 0~i의 (j 범위) 값을 비교하여 v[i]의 first와 second가 각각 v[j]의 first와 second보다 큰 지를 확인한다.

크다면 색종이가 무사히 안에 들어갈 수 있다는 것이므로 dp 값을 갱신시켜준다.

한 번 조건을 만족할때마다 색종이 가능한 갯수가 1개씩 늘어나므로 dp[j]+1을 통해 갱신해준다.

그리고 최대색종이 갯수를 구하는 것이기 때문에 dp[i]에는 최대값이 담기도록 해준다.

이후 dp에 담긴 값중 가장 큰 값을 출력시켜주면 된다.

 

<예제>
7
1 2
8 7
20 10
20 20
15 12
12 14
11 12

-> (앞에가 작은 값, 뒤가 큰 값이 오도록 변경)

1 2
7 8
10 20
20 20
12 15
12 14
11 12

-> (오름차순으로 정렬)

1 2 -> 길이 1
7 8 -> 길이 2
10 20 -> 길이 3 (직후 12 불가능 [20>12])
11 12 -> 길이 3 (직전 [7, 8]에서 연결)
12 14 -> 길이 4
12 15 -> 길이 5
20 20 -> 길이 6