[Silver III] 특별상이라도 받고 싶어 - 24460

문제 링크

성능 요약

메모리: 73104 KB, 시간: 644 ms

분류

분할 정복, 재귀

문제 설명

HCPC 2021에 참석한 $N\times N$$N \times N$명의 사람들이 의자가 정사각형 형태로 배치된 대회장에서 대회를 한다. 모든 의자에는 서로 다른 추첨번호가 적혀있으며 HCPC 2021의 마지막에는 아래에 설명된 규칙에 따라 특별상을 받을 사람 한 명을 정한다.

1. 특별상을 받을 수 있는 사람이 한 명이라면, 그 사람이 뽑힌다.
2. 그렇지 않은 경우, 대회장을 같은 크기의 정사각형 네 개로 나누어 각 구역에서 이 규칙을 재귀적으로 적용해서 구역마다 한 명씩 총 네 명을 뽑는다.
3. 뽑힌 네 명 중 의자에 적힌 추첨번호가 두 번째로 작은 사람이 뽑힌다.

HCPC 2021에 참가한 지원이는 자신의 실력이 부족해서 수상권이 아니라고 생각하였고, 실력과 무관하게 받을 수 있는 특별상을 노리고 있다.

아래 예시를 참고하자.

위와 같은 의자 배열이 있다고 가정하자. 이를 네 개의 구역으로 나누면 아래와 같다.

나누어진 구역의 왼쪽 위 구역을 다시 네 개의 구역으로 나누면 아래와 같다.

여기에서 추첨번호가 두 번째로 낮은 사람을 고르면 아래와 같다.

이와 같은 작업을 모든 영역에 대해 실행하면 아래와 같다.

따라서 특별상을 받는 추첨번호는 아래와 같다.

따라서, 추첨번호 $3$$3$이 적힌 의자에 앉은 참가자가 특별상을 받는다.

의자 각각에 적혀 있는 추첨번호가 주어질 때, 지원이가 HCPC 2021에서 경품을 받을 수 있으려면 어떤 의자에 앉아야 하는지 계산하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 정수 $N$$N$이 주어진다. (단, $N=2^m$$N = 2^m$, $0\le m\le 10$$0 \le m \le 10$, $m$$m$은 정수)

두 번째 줄부터 $N$$N$개 줄의 $i$$i$번째 줄에는 $i$$i$번째 줄에 있는 의자에 적힌 추첨번호가 주어진다. 각 줄에는 $N$$N$개의 추첨번호가 공백으로 구분되어 주어진다.

추첨번호는 $2^{31}$$2^{31}$ 보다 작은 음이 아닌 정수이고, 모든 추첨번호는 서로 다름이 보장된다.

출력

지원이가 HCPC 2021에서 경품을 받기 위해 앉아야 하는 의자에 적힌 추첨번호를 출력한다.

---

풀이

아이디어

절반으로 계속 나누어나가 리스트에 저장한 뒤 오름차순으로 정렬한 후 1번째 인덱스를 리턴한다.
이때 최종 형태가 아니라면 리스트 안에 저장하면서 정복해 나가는 방식이다.

코드

1. WA

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
lst = []

def conquer(g):
    div = len(g) // 2
    if div == 1:
        return(sorted(sum(g, []))[1])

    tmp = [[] for _ in range(div)]     # 1사분면
    for i in range(div):
        for j in range(div):
            tmp[i].append(graph[i][j])
    lst.append(conquer(tmp))

    tmp = [[] for _ in range(div)]    # 2사분면
    for i in range(div, N):
        for j in range(div):
            tmp[i-div].append(graph[i][j])
    lst.append(conquer(tmp))

    tmp = [[] for _ in range(div)]    # 3사분면
    for i in range(div):
        for j in range(div, N):
            tmp[i].append(graph[i][j])
    lst.append(conquer(tmp))

    tmp = [[] for _ in range(div)]     # 4사분면
    for i in range(div, N):
        for j in range(div, N):
            tmp[i-div].append(graph[i][j])
    lst.append(conquer(tmp))
    return(sorted(lst)[1])
print(conquer(graph))

2. SOLVE

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]

def conquer(x, y, n):
    if n == 1:
        return graph[x][y]
    div = n // 2
    lst = [
        conquer(x, y, div),
        conquer(x, y+div, div),
        conquer(x+div, y, div),
        conquer(x+div, y+div, div),
    ]
    return sorted(lst)[1]

print(conquer(0, 0, N))

---

회고

재귀함수의 형태를 구성하는 방법의 아이디어를 떠올리지 못해 첫번째처럼 난해하게 구현하다가 인터넷의 참고로 겨우 풀이한 문제.. 실버 3 따위에 지다니..

재귀의 형태는 생각보다 직관적이고 간단한 형태로 구성되는것 같다. 이를 명심하고 재귀의 형태를 구상하자.