색종이 올려 놓기

색종이 올려 놓기

크기가 모두 다른 직사각형 모양의 색종이가 여러 장 있다. 

색종이를 하나씩 올려 놓아, 되도록 많은 장수의 색종이들을 쌓으려고 한다.

 

새로 한 장의 색종이를 올려 놓을 때는 지금까지 쌓아 놓은 색종이들 중 

맨 위의 색종이 위에 올려놓아야 하며 아래의 두 조건을 모두 만족해야 한다.

 

조건 1 : 새로 올려 놓는 색종이는 맨 위의 색종이보다 크지 않아야 한다.
         즉, 맨 위의 색종이 밖으로 나가지 않아야 한다.

조건 2 : 새로 올려 놓는 색종이와 맨 위의 색종이의 변들은 서로 평행해야 한다.(색종이를 90˚돌려 놓을 수 있다.)

 

예를 들어, 아래의 그림 중에서 위의 두 조건을 모두 만족하는 경우는 (나)뿐이다.

 

 

 

 

 

색종이는 두 변의 길이로 표현된다. (3, 5)는 두 변의 길이가 각각 3과 5인 색종이를 나타낸다.

 

예를 들어, 다음과 같이 7장의 색종이가 주어졌다고 하자 : (1, 2), (8, 7), (20, 10), (20, 20), (15, 12), (12, 14), (11, 12)

위의 조건을 만족하면서 가장 많이 쌓을 수 있는 색종이들의 순서는 (20, 20), (15, 12), (12, 14), (11, 12), (8, 7), (1, 2)이다.

 

입력으로 색종이들이 주어졌을 때, 위의 조건 1과 조건 2를 만족하면서 쌓을 수 있는

최대 색종이 장수를 구하는 프로그램을 작성하시오.

 

 

입력형식

첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다.두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 작은 자연수이다.

 

출력형식

쌓을 수 있는 최대 색종이 장수를 출력한다.

 

입력 예

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

 

출력 예

6

 

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define Swap(a, b) {t = a; a = b; b = t;}

int a[100], b[100], d[100];
int n, ret, t;

int main() 
{
    int i, j;

    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d %d", &a[i], &b[i]);
        
        if (a[i] > b[i])
            Swap(a[i], b[i]);
    }

    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (a[i] > a[j] || (a[i] == a[j] && b[i] > b[j]))
            {
                Swap(a[i], a[j]);
                Swap(b[i], b[j]);
            }
        }
    }

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < i; j++)
        {
            if (a[j] <= a[i] && b[j] <=b[i] && d[i] < d[j])
            {
                d[i] = d[j];
            }
        }
        d[i]++;
        if (d[i] > ret)
            ret = d[i];
    }

    printf("%d\n", ret);

    return 0;
}