www.acmicpc.net/workbook/view/1152 (A형 문제집)
(x, y) → (r, c)로 설명한다.
(r, c)를 기준으로 마름모를 만드는 것이 핵심이다.
(r, c)를 기준으로 d1과 d2를 늘려가면서 선거구를 만든다.
이때, 범위를 체크하는 것보다 벽 = -1 을 만나면 종료하도록 구현하면 편하다.
따라서 input에서 A의 주변을 -1로 만들고 (1, 1)부터 입력을 받자.
#define MAX (20 + 5)
int N;
int MAP[MAX][MAX];
void input()
{
scanf("%d", &N);
for (int r = 0; r <= N + 1; r++)
for (int c = 0; c <= N + 1; c++)
MAP[r][c] = -1;
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
scanf("%d", &MAP[r][c]);
}
모든 선거구에 대해 나눠봐야 하므로, r, c를 이중 for문으로 나눠본다.
이때, 마름모의 최소 크기가 3이므로 r의 범위는 1부터 N - 2가 된다.
마찬가지로 c는 2부터 N - 1까지만 만들어보면 된다.
main은 아래와 같이 구성된다.
int main(void)
{
input();
for (int r = 1; r <= N - 2; r++)
{
for (int c = 2; c <= N - 1; c++)
{
for (int d1 = 1; ; d1++)
{
if (MAP[r + d1][c - d1] == -1) break;
for (int d2 = 1; ; d2++)
{
if (MAP[r + d2][c + d2] == -1 || MAP[r + d1 + d2][c + d2 - d1] == -1) break;
calculate(r, c, d1, d2);
}
}
}
}
printf("%d\n", minAnswer);
return 0;
}
첫 번째, 두 번째 for문으로 r과 c가 결정되면, d1과 d2를 늘려나간다.
경계조건을 보면 마름모의 꼭짓점은 총 4개로 아래와 같다.
위 : MAP[r][c]
왼쪽 : MAP[r + d1][c - d1]
오른쪽 : MAP[r + d2][c + d2]
아래 : MAP[r + d1 + d2][c + d2 - d1]
MAP[][] 가 -1이 될 때까지 d1과 d2를 늘려가면 된다.
for문의 중간은 for문의 수행 조건이다. 따라서 비워두면 아무 조건 없이 계속 수행하게 된다.
물론, d1과 d2를 무작정 늘리면 안되므로, break로 종료하면 된다.
for문의 중간에 수행 조건을 쓰는 것보다 종료 조건으로 break를 하는 것이 더 명확해보여서 중간을 비워두었다.
r, c, d1, d2가 정해져 선거구를 나누었으니 계산하면 된다.
선거구 1 ~ 4는 아주 고맙게도 범위를 문제에서 자세하게 제시해주었다.
하지만 이 조건은 5번 선거구에 포함되지 않은 구역에 대한 조건이므로,
2번 선거구는 (r < c), 3번 선거구는 (c < r) 이라는 조건도 포함되어 있다.
따라서 r과 c가 1 ~ 4에 포함되면 sum[1] ~ sum[4]에 더해주기만 하면 된다.
문제는 위의 범위 조건이 5번 선거구가 아니라는 조건하에만 참이라는 것이다.
따라서 calculate에서는 gerry[][] 배열에 5번 선거구만 따로 표시한다.
5번 선거구가 아니면 1 ~ 4번 선거구이기 때문에 위에 제시한 조건대로 sum을 누적한다.
5번 선거구는 r, c, d1, d2로 간단히 알 수 있다.
int minAnswer = 0x7fff0000;
void calculate(int sr, int sc, int d1, int d2)
{
int gerry[MAX][MAX] = { 0 };
int sum[6] = { 0 };
int start, end, left, right;
int min, max;
start = end = sc;
left = -1, right = 1;
for (int r = sr; r <= sr + d1 + d2; r++)
{
for (int c = start; c <= end; c++) gerry[r][c] = 5;
start += left;
end += right;
if (start == sc - d1) left = 1;
if (end == sc + d2) right = -1;
}
/* 1 ~ 4 구역 배분 및 합 계산 */
/* MIN 갱신 */
}
gerry 2차원 배열을 0으로 초기화하자.
먼저 5번 선거구의 row는 sr부터 sr + d1 + d2이다.
1번 row에서는 column의 처음과 끝이 같다(start = end = sc). 따라서 5는 1칸이다
2번 row는 5가 3칸이다. 왜냐하면 왼쪽은 start가 감소했고, 오른쪽으로 end가 증가하기 때문이다.
따라서 row가 증가할 때마다 left는 1씩 감소하도록, right는 1씩 증가하도록 한다.
어느 조건부터는 왼쪽은 다시 늘어나고 오른쪽은 다시 줄어든다.
그 조건은 왼쪽이 sc - d1이 될 때이고, 오른쪽은 sc + d2가 될 때이다.
따라서 이 조건이 되면 left를 +로 right는 -로 바꿔서 gerry[r][c]에 5를 표시한다.
이렇게 되면 gerry[r][c]가 5번 구역인지 아닌지 판단할 수 있게 된다.
이제 경계 조건을 이용하여 1 ~ 4번 구역을 gerry에 표시한다.
그리고 gerry에 적은 번호를 이용해 sum[gerry[r][c]에 MAP[r][c]를 누적한다.
int minAnswer = 0x7fff0000;
void calculate(int sr, int sc, int d1, int d2)
{
...
// 1
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (gerry[r][c] == 5) break;
if ((1 <= r && r < sr + d1) && (1 <= c && c <= sc)) gerry[r][c] = 1;
}
}
// 2
for (int r = 1; r <= N; r++)
{
for (int c = sc; c <= N; c++)
{
if (gerry[r][c] == 5) continue;
if ((1 <= r && r <= sr + d2) && (sc < c && c <= N)) gerry[r][c] = 2;
}
}
// 3
for (int r = sr; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (gerry[r][c] == 5) break;
if ((sr + d1 <= r && r <= N) && (1 <= c && c < sc - d1 + d2)) gerry[r][c] = 3;
}
}
// 4
for (int r = sr; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (gerry[r][c] == 5) continue;
if ((sr + d2 < r && r <= N) && (sc - d1 + d2 <= c && c <= N)) gerry[r][c] = 4;
}
}
// sum 계산
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
sum[gerry[r][c]] += MAP[r][c];
// min 갱신
}
이제 sum[1] ~ sum[5]의 min과 max를 찾아서 그 차이의 최솟값을 minAnswer에 갱신하면 된다.
최종 코드는 아래를 참고하면 된다.
#include <stdio.h>
#define MAX (20 + 5)
int N;
int MAP[MAX][MAX];
void input()
{
scanf("%d", &N);
for (int r = 0; r <= N + 1; r++)
for (int c = 0; c <= N + 1; c++)
MAP[r][c] = -1;
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
scanf("%d", &MAP[r][c]);
}
void output(int map[MAX][MAX])
{
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
printf("%d ", map[r][c]);
putchar('\n');
}
putchar('\n');
}
int minAnswer = 0x7fff0000;
void calculate(int sr, int sc, int d1, int d2)
{
int gerry[MAX][MAX] = { 0 };
int sum[6] = { 0 };
int start, end, left, right;
int min, max;
start = end = sc;
left = -1, right = 1;
for (int r = sr; r <= sr + d1 + d2; r++)
{
for (int c = start; c <= end; c++) gerry[r][c] = 5;
start += left;
end += right;
if (start == sc - d1) left = 1;
if (end == sc + d2) right = -1;
}
// 1
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (gerry[r][c] == 5) break;
if ((1 <= r && r < sr + d1) && (1 <= c && c <= sc)) gerry[r][c] = 1;
}
}
// 2
for (int r = 1; r <= N; r++)
{
for (int c = sc; c <= N; c++)
{
if (gerry[r][c] == 5) continue;
if ((1 <= r && r <= sr + d2) && (sc < c && c <= N)) gerry[r][c] = 2;
}
}
// 3
for (int r = sr; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (gerry[r][c] == 5) break;
if ((sr + d1 <= r && r <= N) && (1 <= c && c < sc - d1 + d2)) gerry[r][c] = 3;
}
}
// 4
for (int r = sr; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (gerry[r][c] == 5) continue;
if ((sr + d2 < r && r <= N) && (sc - d1 + d2 <= c && c <= N)) gerry[r][c] = 4;
}
}
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
sum[gerry[r][c]] += MAP[r][c];
//for debug
//for (int r = 1; r <= N; r++)
//{
// for (int c = 1; c <= N; c++)
// printf("%d ", gerry[r][c]);
// putchar('\n');
//}
//putchar('\n');
min = 0x7fff0000;
max = -0x7fff0000;
for (int i = 1; i <= 5; i++)
{
if (sum[i] < min) min = sum[i];
if (sum[i] > max) max = sum[i];
}
if (max - min < minAnswer) minAnswer = max - min;
}
int main(void)
{
input();
for (int r = 1; r <= N - 2; r++)
{
for (int c = 2; c <= N - 1; c++)
{
for (int d1 = 1; ; d1++)
{
if (MAP[r + d1][c - d1] == -1) break;
for (int d2 = 1; ; d2++)
{
if (MAP[r + d2][c + d2] == -1 || MAP[r + d1 + d2][c + d2 - d1] == -1) break;
calculate(r, c, d1, d2);
}
}
}
}
printf("%d\n", minAnswer);
return 0;
}
A형 문제의 tc가 여러 개이므로, minAnswer를 초기화하는 코드를 잊지 말자.
'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글
| BOJ 17822 : 원판 돌리기 (삼성 SW TEST A형) (0) | 2021.03.26 |
|---|---|
| BOJ 17837 : 새로운 게임 2 (삼성 SW TEST A형) (0) | 2021.03.23 |
| BOJ 17142 : 연구소 3 (삼성 SW TEST A형) (0) | 2021.03.17 |
| BOJ 17140 : 이차원 배열과 연산 (삼성 SW TEST A형) (0) | 2021.03.14 |
| BOJ 17143 : 낚시왕 (삼성 SW TEST A형) (0) | 2021.03.12 |
댓글