JUNGOL 실력키우기 2259 : 참외밭

보관함 2018. 10. 18. 12:17

시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다.

문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다.

어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다.

유레카! 1㎡의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다.

1㎡의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다.

참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다.

다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다.

밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 모두 측정하였다.

e3050b66a1b29a01767400d7560a4131_1449727

예를 들어 참외밭이 위 그림과 같은 모양이라고 하자. 그림에서 오른쪽은 동쪽, 왼쪽은 서쪽, 아래쪽은 남쪽, 위쪽은 북쪽이다.

이 그림의 왼쪽위 꼭지점에서 출발하여, 반시계방향으로 남쪽으로 30m, 동쪽으로 60m, 남쪽으로 20m,

동쪽으로 100m, 북쪽으로 50m, 서쪽으로 160m 이동하면 다시 출발점으로 되돌아가게 된다.

위 그림의 참외밭 면적은 6800㎡이다. 만약 1㎡의 넓이에 자라는 참외의 개수가 7이라면,

이 밭에서 자라는 참외의 개수는 47600으로 계산된다.

1㎡의 넓이에 자라는 참외의 개수와, 참외밭을 이루는 육각형의 임의의 한 꼭지점에서 출발하여 반시계방향으로 둘레를

돌면서 지나는 변의 방향과 길이가 순서대로 주어진다. 이 참외밭에서 자라는 참외의 수를 구하는 프로그램을 작성하시오.

첫 번째 줄에 1㎡의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K(1≤K≤20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭지점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이 (1 이상 500 이하의 정수) 가 둘째 줄부터 일곱 번째 줄까지 한 줄에 하나씩 순서대로 주어진다. 변의 방향에서 동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4로 나타낸다.

첫째 줄에 입력으로 주어진 밭에서 자라는 참외의 수를 출력한다.

얼핏 보면 어려울 것 같은 문제지만 하나하나 따져보면 크게 복잡한 문제가 아닌것을 알 수 있습니다.

먼저, 참외밭의 모양이 항상 'ㄱ'이므로 주어지는 입력은 항상 6개 입니다.

그러므로 가장 긴 참외밭은 아무리 길어도 1,000m가 될 수 없습니다. 즉, 2000 x 2000 배열을 만들고 중앙을 기준으로 조건에 따라 배열을 채우고 배열을 이용해 넓이를 구하기만 하면 됩니다. 이후 처음 주어진 m^2당 참외 개수를 곱해주면 결과를 얻을 수 있습니다.

위의 가정을 통해 코드를 짰고 넓이 계산은 다음과 같이 진행했습니다.

가로로 진행하는 경우를 제외하고 세로로 진행하는 경우만 저장하여 루프를 돌면서 시작 지점에서 끝 지점까지의 넓이를 더해 최종 넓이를 구했습니다.

결과적으로 넓이 * m^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
#include <iostream>
 
using namespace std;
 
#define NONE -1
 
enum { EAST=1, WEST, SOUTH, NORTH };
 
bool field[2000][2000] {};
 
int main()
{
    int k;
    cin >> k;
 
    int x{ 1000 }, y{ 1000 };
 
    // 참외 밭 정보 입력받기
    for (int i = 0; i < 6; ++i)
    {
        int direction, length;
        cin >> direction >> length;
 
        switch (direction)
        {
        case EAST:
            x += length;
            break;
        case WEST:
            x -= (length - 1);
            break;
        case SOUTH:
            for (int j = 1; j <= length; ++j)
            {
                field[y - j][x] = true;
            }
            y -= length;
            break;
        case NORTH:
            for (int j = 0; j < length; ++j)
            {
                field[y + j][x] = true;
            }
            y += length;
            break;
        }
    }
 
    // 밭의 넓이 구하기
    int fieldExtent{ 0 };
    for (int i = 0; i < 2000; ++i)
    {
        int extentChecker{ NONE };
        for (int j = 0; j < 2000; ++j)
        {
            // 밭의 왼쪽 시작 지점을 찾은 경우
            if (extentChecker == NONE && field[i][j])
            {
                extentChecker = j;
            }
            // 끝 지점이 나오기 전 까지 넓이로 계산한다.
            if (extentChecker != NONE)
            {
                fieldExtent++;
            }
            // 끝 지점을 찾은 경우
            if (extentChecker != NONE && field[i][j])
            {
                // 시작 지점과 같지 않으면 넓이 계산을 중단한다.
                if (extentChecker != j)
                {
                    extentChecker = NONE;
                }
            }
        }
    }
 
    cout << fieldExtent * k << endl;
}
Colored by Color Scripter
cs

해당 문제에 대해서 추가 검토한 결과 끝 지점이 존재하지 않는 경우에 넓이 처리가 제대로 되지 않는 것 같습니다.

그래서 끝 지점이 존재하지 않는 경우는 시작 지점만 있는 경우이므로 넓이에 1만 추가하도록 처리했습니다.

기존에 막혔던 부분은 처리됐는데 새로운 부분에서 문제가 생겼습니다. 알고리즘 자체를 수정할 필요가 있을 것 같습니다.

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
#include <iostream>
 
using namespace std;
 
#define NONE -1
 
enum { EAST=1, WEST, SOUTH, NORTH };
 
bool field[2000][2000] {};
 
int main()
{
    int k;
    cin >> k;
 
    int x{ 1000 }, y{ 1000 };
 
    // 참외 밭 정보 입력받기
    for (int i = 0; i < 6; ++i)
    {
        int direction, length;
        cin >> direction >> length;
 
        switch (direction)
        {
        case EAST:
            x += length;
            break;
        case WEST:
            x -= (length - 1);
            break;
        case SOUTH:
            for (int j = 1; j <= length; ++j)
            {
                field[y - j][x] = true;
            }
            y -= length;
            break;
        case NORTH:
            for (int j = 0; j < length; ++j)
            {
                field[y + j][x] = true;
            }
            y += length;
            break;
        }
    }
 
    // 밭의 넓이 구하기
    int fieldExtent{ 0 };
    for (int i = 0; i < 2000; ++i)
    {
        int addedValue{ 0 };
        int extentChecker{ NONE };
        for (int j = 0; j < 2000; ++j)
        {
            // 밭의 왼쪽 시작 지점을 찾은 경우
            if (extentChecker == NONE && field[i][j])
            {
                extentChecker = j;
            }
            // 끝 지점이 나오기 전 까지 넓이로 계산한다.
            if (extentChecker != NONE)
            {
                addedValue++;
            }
            // 끝 지점을 찾은 경우
            if (extentChecker != NONE && field[i][j])
            {
                // 시작 지점과 같지 않으면 넓이 계산을 중단한다.
                if (extentChecker != j)
                {
                    extentChecker = NONE;
                    break;
                }
            }
        }
        // 시작지점과 끝 지점 사이의 넓이를 더한다.
        if (extentChecker == NONE)
        {
            fieldExtent += addedValue;
        }
        // 만약 끝 지점이 없었다면 시작 지점만 존재하는 경우이므로 넓이에 1만 더한다.
        else
        {
            fieldExtent += 1;
        }
    }
 
    cout << fieldExtent * k << endl;
}
Colored by Color Scripter
cs

알고리즘을 변경하여 전체 크기에서 비게 되는 부분을 제거하는 방법을 생각했습니다.

결국 모든 모양이 ㄱ자 이므로 x, y의 가장 긴 길이를 찾고 x, y 모두 길이가 모자라는 부분이 안쪽 사각형의 꼭지점일 것이라고 생각했습니다.

그리고 내부 사각형을 구현하기 위해 어느 방향으로 잘라야 하는지 결정해야 했습니다.

가령 ㄱ인 경우 왼쪽 아래를 잘라야하고 ㄴ인 경우 왼쪽 위를 잘라햐 합니다.

이를 위해서 아래 그림처럼 y의 방향을 구하기 위해 동일한 x를 사용하는 정점의 x가 현재 x좌표보다 왼쪽인 경우 안쪽 사각형의 길이는 전체 현재 좌표를 그대로 사용하고 오른쪽인 경우 전체 길이 - 현재 좌표를 y의 길이로 적용했습니다.

동일한 과정을 y와 x만 바꿔서 적용하면 안쪽 사각형의 x길이를 구할 수 있습니다.

결과적으로 외부 사각형에서 내부 사각형을 빼는 방식으로 밭의 길이를 구했고 결과에 밭 크기당 수확 량을 곱해 결과를 냈습니다.

결과는 사실 동일했습니다. 3번째 케이스에서 막혔는데, 이번에는 어떤게 문제가 된건지 감이 안잡히네요.

그래도 향상이 있었는데, 실행 속도와 메모리 사용량에서 성과를 얻었습니다.

이전 알고리즘에 비해 메모리는 1/5, 속도는 6~7배 빨라졌습니다.

속도와 공간 효율성 측면에서는 이 방향이 적절한 것 같은데 정확하게 어떤게 문제인지를 파악해봐야 할 것 같습니다.

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
106
107
108
109
110
111
#include <iostream>
 
using namespace std;
 
enum Direction{ East = 1, West, South, North };
 
struct POINT
{
    int x{ 0 }, y{ 0 };
};
 
int main()
{
    int k;
    cin >> k;
 
    // 입력된 정점을 확인하기 위한 배열
    POINT pointArr[6];
    int maxX{ 0 }, maxY{ 0 };
 
    POINT curPos;
    for (int i = 0; i < 6; ++i)
    {
        int direction, distance;
        cin >> direction >> distance;
 
        switch (direction)
        {
        case East:
            curPos.x += distance;
            break;
        case West:
            curPos.x -= distance;
            break;
        case South:
            curPos.y -= distance;
            break;
        case North:
            curPos.y += distance;
            break;
        }
        // 이동한 지점을 저장한다.
        pointArr[i] = curPos;
 
        // 절대값이 가장 큰 요소를 각각 찾는다.
        if (abs(curPos.x) > maxX)
        {
            maxX = abs(curPos.x);
        }
        if (abs(curPos.y) > maxY)
        {
            maxY = abs(curPos.y);
        }
    }
 
    int maxExtent{ abs(maxX * maxY) };
    int smallExtent{ 0 };
    for (int i = 0; i < 5; ++i)
    {
        if (pointArr[i].x == 0 || pointArr[i].y == 0) continue;
        
        // 모든 지점이 가장 긴 선분보다 짧은 지점을 찾는다.
        if (maxX > abs(pointArr[i].x) && maxY > abs(pointArr[i].y))
        {
            // 제외 해야할 부분의 선분 길이를 구한다.
            int xLength{ };
            int yLength{ };
 
            // 동일한 y선상에 위치한 점을 찾는다.
            for (int j = 0; j < 5; ++j)
            {
                if (i != j && pointArr[i].y == pointArr[j].y)
                {
                    // 현재 좌표가 동일 선상의 x보다 크면
                    // ㄱ 또는 ┛ 일 것이다.
                    if (pointArr[i].x > pointArr[j].x)
                    {
                        xLength = maxX - abs(pointArr[i].x);
                    }
                    // 반대의 경우 ㄴ 또는 ┏일 것이다.
                    else
                    {
                        xLength = abs(pointArr[i].x);
                    }
                }
            }
 
            // 동일한 과정을 통해 y길이를 찾는다.
            for (int j = 0; j < 5; ++j)
            {
                if (i != j && pointArr[i].x == pointArr[j].x)
                {
                    if (pointArr[i].y > pointArr[j].y)
                    {
                        yLength = abs(pointArr[i].y);
                    }
                    else
                    {
                        yLength = maxY - abs(pointArr[i].y);
                    }
                }
            }
 
            // 제외 해야할 부분의 넓이를 구한다.
            smallExtent = xLength * yLength;
            break;
        }
    }
 
    cout << (maxExtent - smallExtent) * k << endl;
}
Colored by Color Scripter
cs

이전에 수행한 결과에서 입력되는 값들을 모두 1사분면으로 옮겨서 처리하면 될 것 같아서 해당 작업을 처리하고

반복되는 부분을 조금 정리했습니다.

뭐 결과적으로는 또 완벽하게 통과하지 못했으나 약간의 성능향상을 얻을 수 있었습니다.

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
 
using namespace std;
 
enum Direction{ East = 1, West, South, North };
 
struct POINT
{
    int x{ 0 }, y{ 0 };
};
 
int main()
{
    int k;
    cin >> k;
 
    // 입력된 정점을 확인하기 위한 배열
    POINT pointArr[6];
    int maxX{ 0 }, maxY{ 0 };
 
    POINT curPos;
    for (int i = 0; i < 6; ++i)
    {
        int direction, distance;
        cin >> direction >> distance;
 
        switch (direction)
        {
        case East:
            curPos.x += distance;
            break;
        case West:
            curPos.x -= distance;
            break;
        case South:
            curPos.y -= distance;
            break;
        case North:
            curPos.y += distance;
            break;
        }
        // 이동한 지점을 저장하고 항상 1사분면에 위치하도록 한다.
        pointArr[i].x = abs(curPos.x);
        pointArr[i].y = abs(curPos.y);
 
        // 절대값이 가장 큰 요소를 각각 찾는다.
        if (pointArr[i].x > maxX)
        {
            maxX = pointArr[i].x;
        }
        if (pointArr[i].y > maxY)
        {
            maxY = pointArr[i].y;
        }
    }
 
    int maxExtent{ maxX * maxY };
    int smallExtent{ 0 };
    for (int i = 0; i < 5; ++i)
    {
        if (pointArr[i].x == 0 || pointArr[i].y == 0) continue;
        
        // 모든 지점이 가장 긴 선분보다 짧은 지점을 찾는다.
        if (maxX > abs(pointArr[i].x) && maxY > abs(pointArr[i].y))
        {
            // 제외 해야할 부분의 선분 길이를 구한다.
            int xLength{ };
            int yLength{ };
 
            int sameXindex{ 0 };
            int sameYindex{ 0 };
 
            // 동일한 x선상에 위치한 점을 찾는다.
            for (int j = 0; j < 5; ++j)
            {
                if (i != j && pointArr[i].x == pointArr[j].x)
                {
                    sameXindex = j;
                    break;
                }
            }
            // 동일한 y선상에 위치한 점을 찾는다.
            for (int j = 0; j < 5; ++j)
            {
                if (i != j && pointArr[i].y == pointArr[j].y)
                {
                    sameYindex = j;
                    break;
                }
            }
 
            // 현재 좌표가 동일 선상의 x보다 크면
            // ㄱ 또는 ┛ 일 것이다.
            if (pointArr[i].x > pointArr[sameYindex].x)
            {
                // 현재 좌표가 동일 선상의 y보다 크면 ㄱ
                if (pointArr[i].y > pointArr[sameXindex].y)
                {
                    xLength = pointArr[i].x;
                    yLength = pointArr[i].y;
                }
                // 반대의 경우 ┛
                else
                {
                    xLength = pointArr[i].x;
                    yLength = maxY - pointArr[i].y;
                }
            }
            // 반대의 경우 ㄴ 또는 ┏일 것이다.
            else
            {
                // 현재 좌표가 동일 선상의 y보다 크면 ┏
                if (pointArr[i].y > pointArr[sameXindex].y)
                {
                    xLength = maxX - pointArr[i].x;
                    yLength = pointArr[i].y;
                }
                // 반대의 경우 ㄴ
                else
                {
                    xLength = maxX - pointArr[i].x;
                    yLength = maxY - pointArr[i].y;
                }
            }
 
            // 제외 해야할 부분의 넓이를 구한다.
            smallExtent = xLength * yLength;
            break;
        }
    }
 
    cout << (maxExtent - smallExtent) * k << endl;
}
Colored by Color Scripter
cs

위에서 실패한 문제를 실제로 그려보니 다음과 같은 그림이 나오네요.

즉, 시작 위치를 0, 0으로 가정하고 0보다 작아질 때 반전 해서(-1을 곱해서) 위치를 정하다 보니 위 같은 경우에 문제가 발생할 수 밖에 없었던 거죠.

그러므로 입력된 위치 중 minX와 minY를 구해 이 값이 0보다 작아지면 해당 값을 반전해서 각 위치에 더해주면 깔끔하게 1사분면에 들어가게 될겁니다.

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <iostream>
 
using namespace std;
 
enum Direction{ East = 1, West, South, North };
 
struct POINT
{
    int x{ 0 }, y{ 0 };
};
 
int main()
{
    int k;
    cin >> k;
 
    // 입력된 정점을 확인하기 위한 배열
    POINT pointArr[6];
    int minX{ 0 }, minY{ 0 };
    int maxX{ 0 }, maxY{ 0 };
 
    POINT curPos;
    for (int i = 0; i < 6; ++i)
    {
        int direction, distance;
        cin >> direction >> distance;
 
        switch (direction)
        {
        case East:
            curPos.x += distance;
            break;
        case West:
            curPos.x -= distance;
            break;
        case South:
            curPos.y -= distance;
            break;
        case North:
            curPos.y += distance;
            break;
        }
        // 이동한 지점을 저장한다.
        pointArr[i].x = curPos.x;
        pointArr[i].y = curPos.y;
 
        // 가장 작은 요소를 찾는다.
        if (minX > pointArr[i].x)
        {
            minX = pointArr[i].x;
        }
        else if (minY > pointArr[i].y)
        {
            minY = pointArr[i].y;
        }
    }
 
    // 각 위치를 1사분면으로 보정한다.
    for (int i = 0; i < 6; ++i)
    {
        // 1사분면에서 벗어난 만큼 더해서 1사분면에 위치하게 한다.
        if (minX < 0)
        {
            pointArr[i].x += (-minX);
        }
        if (minY < 0)
        {
            pointArr[i].y += (-minY);
        }
 
        // 각 요소의 최대값을 찾는다.
        if (maxX < pointArr[i].x)
        {
            maxX = pointArr[i].x;
        }
        if (maxY < pointArr[i].y)
        {
            maxY = pointArr[i].y;
        }
    }
 
    int maxExtent{ maxX * maxY };
    int smallExtent{ 0 };
    for (int i = 0; i < 6; ++i)
    {
        if (pointArr[i].x == 0 || pointArr[i].y == 0) continue;
        
        // 모든 지점이 가장 긴 선분보다 짧은 지점을 찾는다.
        if (maxX > abs(pointArr[i].x) && maxY > abs(pointArr[i].y))
        {
            // 제외 해야할 부분의 선분 길이를 구한다.
            int xLength{ };
            int yLength{ };
 
            int sameXindex{ 0 };
            int sameYindex{ 0 };
 
            // 동일한 x선상에 위치한 점을 찾는다.
            for (int j = 0; j < 6; ++j)
            {
                if (i != j && pointArr[i].x == pointArr[j].x)
                {
                    sameXindex = j;
                    break;
                }
            }
            // 동일한 y선상에 위치한 점을 찾는다.
            for (int j = 0; j < 6; ++j)
            {
                if (i != j && pointArr[i].y == pointArr[j].y)
                {
                    sameYindex = j;
                    break;
                }
            }
 
            // 현재 좌표가 동일 선상의 x보다 크면
            // ㄱ 또는 ┛ 일 것이다.
            if (pointArr[i].x > pointArr[sameYindex].x)
            {
                // 현재 좌표가 동일 선상의 y보다 크면 ㄱ
                if (pointArr[i].y > pointArr[sameXindex].y)
                {
                    xLength = pointArr[i].x;
                    yLength = pointArr[i].y;
                }
                // 반대의 경우 ┛
                else
                {
                    xLength = pointArr[i].x;
                    yLength = maxY - pointArr[i].y;
                }
            }
            // 반대의 경우 ㄴ 또는 ┏일 것이다.
            else
            {
                // 현재 좌표가 동일 선상의 y보다 크면 ┏
                if (pointArr[i].y > pointArr[sameXindex].y)
                {
                    xLength = maxX - pointArr[i].x;
                    yLength = pointArr[i].y;
                }
                // 반대의 경우 ㄴ
                else
                {
                    xLength = maxX - pointArr[i].x;
                    yLength = maxY - pointArr[i].y;
                }
            }
 
            // 제외 해야할 부분의 넓이를 구한다.
            smallExtent = xLength * yLength;
            break;
        }
    }
 
    cout << (maxExtent - smallExtent) * k << endl;
}
Colored by Color Scripter
cs

JUNGOL) 문제은행) 실력키우기) 참외밭

저작자표시 비영리 변경금지

ABOUT ME

무제 무제

티스토리툴바

ABOUT ME

관련글 관련글 더보기

티스토리툴바