DY N DY

실력키우기 색종이(고)(C++) 본문

PARK/ALGORITHM

실력키우기 색종이(고)(C++)

손세지 2016. 9. 29. 00:00

1124 : 색종이(고)

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 390 회    시도횟수: 1418 회   



가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 도화지에서 검은색 직사각형을 잘라내려고 한다. 직사각형 또한 그 변이 도화지의 변과 평행하도록 잘라내어야 한다.

 

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 <그림 1>과 같은 모양으로 붙였다. <그림 1>에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 22×5=110이 된다.

 

e3050b66a1b29a01767400d7560a4131_1449727 e3050b66a1b29a01767400d7560a4131_1449727
 

반면 <그림 2>에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 8×15=120이 된다.

 

검은색 색종이의 수와 각 색종이를 붙인 위치가 주어질 때 잘라낼 수 있는 검은색 직사각형의 최대 넓이를 구하는 프로그램을 작성하시오.

 

*주의. 직사각형은 정사각형을 포함한다.

 

첫째 줄에 색종이의 수가 주어진다.
이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다.
색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다.

색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다.



첫째 줄에 잘라낼 수 있는 검은색 직사각형의 최대 넓이를 출력한다.


 [Copy]
3
3 7
15 7
5 2
 [Copy]
120




출처 : KOI 본선 2007 고2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/**************************************************************
    Problem: 1124
    User: a132034
    Language: C++
    Result: Success
    Time:2 ms
    Memory:1140 kb
****************************************************************/
 
 
#include    <cstdio>
#pragma warning(disable:4996)
 
int paper[111][111];
int H[111];
int main()
{
    int max = 1;
    int N;
    scanf("%d", &N);
 
    for (int i = 1; i <= N; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        for (int a = x; a < x + 10; ++a)
            for (int b = y; b < y + 10; ++b)
                paper[a][b] = 1;
    }
 
    for (int i = 2; i <= 100; ++i)
    {
        for (int j = 2; j <= 100; ++j)
        {
            if (paper[i][j] == 1)
                paper[i][j] += paper[i][j - 1];
        }
    }
    for (int i = 1; i <= 100; ++i)
    {
        for (int j = 1; j <= 100; ++j)
        {
            if (paper[i][j] != 0)
            {
                int width = 0;
                int height = 1;
                for (int k = 1; k <= 100; ++k)
                    H[k] = 0;
 
                for (int k = j - paper[i][j] + 1; k <= j; ++k)
                {
                    H[k] = paper[i][k];
                    if (H[k] > 0)
                        width++;
                }
 
                bool flg = true;
                for (int h = i - 1; h > 0; --h)
                {
                    for (int k = j - paper[i][j] + 1; k <= j; ++k)
                    {
                        if (H[k] > 0 && paper[h][k] > 0)
                            continue;
                        else
                        {
                            flg = false;
                            break;
                        }
                    }
                    if (flg)
                        height++;
                    else
                        break;
                }
                flg = true;
                for (int h = i+1; h <= 100; ++h)
                {
                     
                    for (int k = j - paper[i][j] + 1; k <= j; ++k)
                    {
                        if (H[k] > 0 && paper[h][k] > 0)
                            continue;
                        else
                        {
                            flg = false; 
                            break;
                        }
                    }
                    if (flg)
                        height++;
                    else
                        break;
                }
 
                if (max < height * width)
                    max = height * width;
            }
        }
    }
 
 
    printf("%d\n", max);
 
    return 0;
}
cs


실력키우기 남은 두 문제 중 한개... 이제 하나만 더 풀면 실력키우기를 다 푼게 된다. 드디어 ㅠㅠ

이 문제는 사실 이렇게 막 풀면 풀 수도 있긴 한데 더 짧게 뭔가 더 생각을 하면 더 효율적으로 풀 수 있을 것 같다. 


일단 이 문제를 푼 방법은 


1. 각 점에 대하여 x축으로 0부터 현재 위치까지 가장 큰 가로 길이를 구한다. 

2. 각 점마다 y축으로 위 아래 둘다 동일하게 가로를 가졌는지 확인하며 높이를 구한다. 

모든 점에 대하여 이런 과정을 거치면 각 점에 대한 결과가 나오게 된다. 


예제 입력을 그림으로 나타내 보면(100 x 100으로 나타내면 너무 크기 때문에 30 x 30정도로 나타내면)


0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0


사실 배열로 하면 위의 코드에서 paper[x][y]이기 때문에 그림과 x축은 동일하나 y축은 반대가 된다... 

때문에 위와 같은 모양이 된다. 


이때 각 점(색종이가 있는 점 - 1)에 대하여 x축으로 얼마나 긴지 확인하는 로직이 36라인과 같다. 

이렇게 모든 점에 대해 좌측으로부터 자신까지의 가장 긴 x길이를 구하고 나면 

각 점에 대해 위쪽, 아래쪽으로 각각 검색해보며 이 길이를 만족하는지 확인하는 로직이 각각 58, 76의 for loop이다. 


이렇게 구한 width, height를 곱하면 각 점에서의 최대 직사각형 넓이가 된다. 


내가 봐도 코드가 너무 실수할 구석이 많다... 뭔가 더 쉬운 방법이 있을 것 같다. 

저작자표시 동일조건

'PARK > ALGORITHM' 카테고리의 다른 글

알고리즘 & BOJ 2616 소형기관차(C++)  (2) 2016.10.21
BOJ 9251 LCS(C++)  (1) 2016.10.11
실력키우기 연속부분최대곱(C++)  (1) 2016.09.28
koitp 세금(TAX)(C++)  (0) 2016.09.27
실력키우기 하노이의 탑(C++)  (0) 2016.09.27
'PARK/ALGORITHM' Related Articles more