[BOJ] 28128. 현대모비스 특별상의 주인공은?

BOJ 28128. 현대모비스 특별상의 주인공은?
2023 아주대학교 프로그래밍 경시대회 APC Div.1 D번
Ad Hoc

https://www.acmicpc.net/problem/28128

28128번: 현대모비스 특별상의 주인공은?

1. 문제 설명

2023 아주대학교 프로그래밍 경시대회 - Division 1의 D번 문제이다.

가로 길이가 M이고 세로 길이가 N인 격자판으로 추첨판을 덮는데,

해당 격자판에 floor((a*b+1)/2)번 이름이 적힌 학생이 있다면 이름을 출력하면 된다.

만약, 아무도 받을 수 없다면 MANIPULATED (이거 조작이야!!)를 출력하면 된다.

 

예를 들어서, 아래와 같이 추첨판이 있다고 가정하자.

2 3
mobis mobis hyundai
mobis leomessi hyundai

이때의 출력은 다음과 같다.

hyundai
mobis

대체 어떤 규칙으로 이러한 결과가 나왔을까.. 

 

+참고로 코테에서 특별상을 이러한 방식으로 추첨하지는 않았다.

---

2. 문제 접근

이 문제의 포인트는 floor((a*b+1)/2)를 이해하는 것이다.

 

아래에서 두 가지 패턴으로 나눠서 설명할 것인데,결론부터 말하자면 첫 번째 경우는 두 개가 나란히 붙어있으면 당첨된다.

mobis

mobis

: mobis가 당첨된 경우

 

그리고 두 번째 경우는 한 칸을 떨어뜨리고 존재하면 된다.

mobis

messi

mobis

: mobis가 당첨된 경우

 

 

상세한 설명을 위해 사이즈가 무제한인 추첨판에 격자 크기가 (a, b)라고 가정하자.

해당 격자판에서 당첨되려면 아래와 같이 두 가지 경우 중 하나를 만족해야 한다.

 

1. a와 b 둘 중 최소 하나가 짝수인 경우 (격자판의 가로와 세로 중 짝수가 존재하는 경우)

: mobis가 최악으로 당첨되는 경우는 mobis가 지그재그로 존재하고,

mobis		mobis		mobis
	mobis		mobis
mobis		mobis		mobis
	mobis		mobis

나머지 빈 칸 아무대나 mobis가 들어있으면 된다.

이렇게 해야 floor((a*b+1)/2)이상 이름이 나오므로 당첨된다.

 

이때, 격자판의 크기가 (1, 2) 혹은 (2, 1)인 경우로 축소해보면 mobis가 붙어있어야 한다는 말이 된다.따라서 같은 이름이 나란히 붙어있는 경우 반드시 당첨된다.

 

2. a와 b 둘 다 모두 홀수인 경우 (격자판의 가로와 세로가 모두 홀수인 경우): mobis가 최악으로 당첨되는 경우는 mobis가 각 꼭짓점을 차지하며 지그재그로 존재하는 것이다.

mobis		mobis		mobis
	mobis		mobis
mobis		mobis		mobis
	mobis		mobis
mobis		mobis		mobis

이렇게 배치된 경우, floor((a*b+1)/2)이상 이름이 나오므로 당첨된다.

이때, 격자판의 크기가 (1, 3) 혹은 (3, 1)인 경우로 축소해보면 mobis가 한 칸 간격을 갖고 양 옆에 존재해도 당첨된다.

 

중복된 것을 탐색하지 않게 하려고 set을 사용했다.

따라서 당첨된 이름을 set에 넣어두고, 이후 출력할 때 list로 바꾸고 정렬하면 된다.

 

---

3. 구현 코드

from sys import stdin

n, m = map(int, stdin.readline().split())
board = [list(stdin.readline().strip().split()) for _ in range(n)]
tmp = set()
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

# 첫 번째 경우
for x in range(n):
    for y in range(m):
        if board[x][y] not in tmp:
            for i in range(4):
                nx = x + move[i][0]
                ny = y + move[i][1]
                if 0 <= nx < n and 0 <= ny < m:
                    if board[nx][ny] == board[x][y]:
                        tmp.add(board[x][y])
                        break

# 두 번째 경우
if n >= 3:
    for x in range(n-2):
        for y in range(m):
            if board[x][y] not in tmp:
                if board[x][y] == board[x+2][y]:
                    tmp.add(board[x][y])

if m >= 3:
    for x in range(n):
        for y in range(m-2):
            if board[x][y] not in tmp:
                if board[x][y] == board[x][y+2]:
                    tmp.add(board[x][y])

res = sorted(list(tmp))
if res:
    for i in res:
        print(i)
else:
    print('MANIPULATED')

구현 자체는 어렵지 않은데 문제 이해가 어려웠던 문제였다.

그리고 Ad Hoc 문제를 많이 풀어보지 않아서 두 번째 경우 예외처리하는 것이 생각보다 힘들었다..