Sign in Subscribe
PS

[PS] BOJ 33993 / 지정좌석제

Minjun Kim

• 3 min read
[PS] BOJ 33993 / 지정좌석제
문제 링크: https://www.acmicpc.net/problem/33993
Thumbnail: Photo by Hiroyoshi Urushima (Unsplash)

예제 입력을 잘 보도록 합시다..

풀이

누적 합

\(R \times C\) 크기의 좌석에 임의의 위치에 \(N\)명의 친구가 앉아 있습니다. 각 좌석을 중심으로 주변 \(W \times W\) (단, \(W\)는 홀수) 안에 있는 친구의 수를 그 좌석의 만족도라고 합니다. 가장 만족도가 높은 좌석을 찾으려면 결국 모든 좌석에 대해 만족도 계산을 진행해야 하는데, 매 좌석마다 \(W \times W\) 범위의 좌석을 직접 세어보게 되면 시간 초과가 발생합니다.

비록 2차원 배열이지만, 누적 합을 구해서 계산을 줄일 수 있습니다!

2차원 배열에 대해서는 누적 합을 어떻게 계산할지 고민해봤는데, 면적으로 생각하면 이해가 편했습니다. 그림으로 보면 다음과 같습니다.

\(x, y\)까지의 누적 합을 \(1, 1\)부터 \(x, y\)까지의 모든 좌석에 앉아있는 친구 수라고 정의하면, 임의의 구간 \(a, b\), \(c, d\) 사이의 범위에 앉아있는 친구 수는 아래와 같이 구할 수 있습니다.

ab_cd = prefix_sum[c][d] - prefix_sum[c-a-1][d] - prefix_sum[c][d-b-1] + prefix_sum[c-a-1][d-b-1]

그림으로 보면 다음과 같습니다.

아래 코드에서는 중심 좌표를 기준으로 계산하기 위해 식이 조금 변형되었습니다.

입력에 주의

​입력으로 \(N\)명의 친구들의 \(x\), \(y\) 좌표가 주어지는데, 저는 이걸 \(x\)를 가로, \(y\)를 세로 좌표로 생각하고 풀었다가 IndexError를 마주했습니다...

나중에 예제 입력을 설명하는 그림을 같이 보고 \(x\)가 전체 좌석 행렬의 '행'을, \(y\)가 행렬의 '열'을 나타내는 것을 뒤늦게 깨달았습니다... 이거 고치고 바로 맞았습니다 ㅎㅎ;

전체 코드

input = open(0).readline
N, R, C, W = map(int, input().split())

SEATS = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
for _ in range(N):
    x, y = map(int, input().split())
    SEATS[x][y] = 1

# 누적 합 계산
# prefix_sum[y][x]는 (1,1)부터 (x, y)까지의 모든 좌석의 인원수의 합이다. (누적합)
prefix_sum = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
for r in range(1, R + 1):
    for c in range(1, C + 1):
        prefix_sum[r][c] = prefix_sum[r-1][c] + prefix_sum[r][c-1] - prefix_sum[r-1][c-1] + SEATS[r][c]

result_sum = 0
result_x = C + 1
result_y = R + 1
half = W >> 1
for x in range(1, R + 1):
    for y in range(1, C + 1):
        if SEATS[x][y] != 0: # 이미 친구가 앉아 있는 자리이므로 사용 불가.
            continue
        
        left = max(y - half, 1)
        right = min(y + half, C)
        up = max(x - half, 1)
        down = min(x + half, R)
        total = prefix_sum[down][right] - prefix_sum[up - 1][right] - prefix_sum[down][left - 1] + prefix_sum[up - 1][left - 1]   # 중복으로 빼진 부분은 다시 더한다.
        if total > result_sum or total == result_sum and ((x < result_x) or (x == result_x and y < result_y)):
            result_sum = total
            result_x = x
            result_y = y

print(f"{result_sum}\n{result_x} {result_y}")

solution.py