더블릿_색종이 올려놓기

DP를 통해서 답을 도출해야되는 문제였는데, 

나는 생각해내지 못 해서 안타깝다. 같은 스터디를 하는 사람 코드와 설명을 듣고 풀게 되었다. 

문제정리)

다음의 두 조건을 만족시키게 색종이를 쌓아야 한다. 

1) 새로 올려 놓는 색종이는 맨 위의 색종이보다 크지 않아야한다. 맨 위의 색종이 밖으로 나가서는 안 된다. 

2) 새로 올려 놓는 색종이와 맨 위의 색종이의 변들은 서로 평행해야 한다. (색종이를 90도로 회전은 가능하다)

문제풀이)

입력으로 주어지는 색종이들의 개수의 제한은 100개이다. 

모든 경우의 수를 완전탐색으로 할려고 했는데 좋은 방법은 아닌거 같다고 생각했다. 

우선 몇 가지 이슈에 대해서 정리해보자면, 

구조체를 정렬해야 한다. 

근데 문제에서 가로(x), 세로(y)의 입력이 주어지는데 

색종이는 90도로 회전 가능하다고 했으므로 x와 y가 바뀔 수 있고, 그 순서가 큰 의미가 없다고 판단 할 수 있겠다.

그래서 입력의 가로 세로 중 큰 값을 x에, 작은 값을 y에 넣어주었다. 

또는 그 반대로 해도 상관 없다.  

그리고 다음과 같은 방법으로 구조체를 정렬해주는 팁이 있는데, 진선이를 통해서 알게 됐다.

#include <iostream>
#include <algorithm>
using namespace std;
 
struct paper{
    int x, y;
    bool operator()(paper a, paper b){
        if (a.x < b.x) return 1;
        else if (a.x == b.x) return 1;
        else return 0;
    }
};
paper arr[101];
void print(){
    for (int i = 0; i < 6; i++){
        cout << "x : " << arr[i].x << ", y : "<< arr[i].y << endl;
    }
}
int main(){
    arr[0].x = 10; arr[0].y = 1;
    arr[1].x = 9; arr[1].y = 2;
    arr[2].x = 8; arr[2].y = 3;
    arr[3].x = 7; arr[3].y = 4;
    arr[4].x = 6; arr[4].y = 5;
    arr[5].x = 5; arr[5].y = 6;
    
    // 정렬 전
    cout << "정렬 전" << endl;
    print();
 
    sort(arr, arr + 6, paper());
    
    // 정렬 후
    cout << "정렬 전" << endl;
    print();
 
    return 0;
}
 

위 방법은 구조체를 작은 수를 앞쪽(오름차순으로 정렬을 하고자 할 때 사용한다)

이 방법은 <algorithm>헤더의 sort를 충분히 이용 할 수 있어서 좋은 것 같다. 

이렇게 준비가 다 끝나면 

첫번째 색종이 이후에 두번째 색종이부터 순회하면서 

매번 자신 색종이 전까지를 체크하면서 

앞의 색종이보다 자신이 크면 색종이 쌓는 개수를 1개씩 증가시켜주어 결과값에 저장시켜주는 

메모리에 저장하는 일종의 dp방법을 사용하여 답을 구해주면 된다. 

    sort(arr, arr + paper_num, paper());
    for (int i = 1; i<paper_num; i++){
        for (int j = 0; j<i; j++){
            if (arr[i].x >= arr[j].x && result[i]<result[j] + 1)
                result[i] = result[j] + 1;
        }
    }
    sort(result, result + paper_num);
    maxpaper = result[paper_num - 1] + 1;