본문 바로가기
IT 톺아보기/알고리즘

백준 23291번 | 어항 정리 - python

by 파초우 2022. 10. 13.
반응형
 

23291번: 어항 정리

마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바

www.acmicpc.net

문제

마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바닥 위에 놓여져 있다. 어항에는 물고기가 한 마리 이상 들어있다. <그림 1>은 어항 8개가 바닥 위에 놓여있는 상태이며, 칸에 적힌 값은 그 어항에 들어있는 물고기의 수이다. 편의상 어항은 정사각형으로 표현했다.

<그림 1>

어항을 한 번 정리하는 과정은 다음과 같이 이루어져 있다.

먼저, 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다. 만약, 그러한 어항이 여러개라면 물고기의 수가 최소인 어항 모두에 한 마리씩 넣는다. 위의 예시의 경우 물고기의 수가 가장 적은 어항에는 물고기가 2마리 있고, 그러한 어항은 2개가 있다. 따라서, 2개의 어항에 물고기를 한 마리씩 넣어 <그림 2>와 같아진다.

<그림 2>

이제 어항을 쌓는다. 먼저, 가장 왼쪽에 있는 어항을 그 어항의 오른쪽에 있는 어항의 위에 올려 놓아 <그림 3>이 된다.

<그림 3>

이제, 2개 이상 쌓여있는 어항을 모두 공중 부양시킨 다음, 전체를 시계방향으로 90도 회전시킨다. 이후 공중 부양시킨 어항을 바닥에 있는 어항의 위에 올려놓는다. 바닥의 가장 왼쪽에 있는 어항 위에 공중 부양시킨 어항 중 가장 왼쪽에 있는 어항이 있어야 한다. 이 작업은 공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 있을때까지 반복한다.

먼저, <그림 4>와 같이 어항이 놓인 상태가 변하고, 한 번 더 변해서 <그림 5>가 된다.

<그림 4>

<그림 5>

<그림 5>에서 한 번 더 어항을 공중 부양시키는 것은 불가능하다. 그 이유는 <그림 6>과 같이 공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 없기 때문이다.

<그림 6>

공중 부양 작업이 모두 끝나면, 어항에 있는 물고기의 수를 조절한다.

모든 인접한 두 어항에 대해서, 물고기 수의 차이를 구한다. 이 차이를 5로 나눈 몫을 d라고 하자. d가 0보다 크면, 두 어항 중 물고기의 수가 많은 곳에 있는 물고기 d 마리를 적은 곳에 있는 곳으로 보낸다. 이 과정은 모든 인접한 칸에 대해서 동시에 발생한다. 이 과정이 완료되면 <그림 7>이 된다.

<그림 7>

이제 다시 어항을 바닥에 일렬로 놓아야 한다. 가장 왼쪽에 있는 어항부터, 그리고 아래에 있는 어항부터 가장 위에 있는 어항까지 순서대로 바닥에 놓아야 한다. <그림 8>이 바닥에 다시 일렬로 놓은 상태이다.

<그림 8>

다시 공중 부양 작업을 해야 한다. 이번에는 가운데를 중심으로 왼쪽 N/2개를 공중 부양시켜 전체를 시계 방향으로 180도 회전 시킨 다음, 오른쪽 N/2개의 위에 놓아야 한다. 이 작업은 두 번 반복해야한다. 두 번 반복하면 바닥에 있는 어항의 수는 N/4개가 된다. <그림 9>는 이 작업을 1번 했을 때, <그림 10>은 다시 한 번 더 했을 때이다.

<그림 9>

<그림 10>

여기서 다시 위에서 한 물고기 조절 작업을 수행하고, 바닥에 일렬로 놓는 작업을 수행한다. <그림 10>에서 조절 작업을 마친 결과는 <그림 11>이 되고, 여기서 다시 바닥에 일렬로 놓는 작업을 수행하면 <그림 12>가 된다.

<그림 11>

<그림 12>

어항의 수 N, 각 어항에 들어있는 물고기의 수가 주어진다. 물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하가 되려면 어항을 몇 번 정리해야하는지 구해보자.

입력

첫째 줄에 N, K가 주어진다. 둘째에는 어항에 들어있는 물고기의 수가 가장 왼쪽에 있는 어항부터 순서대로 주어진다.

출력

 물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하가 되려면 어항을 몇 번 정리해야하는지 출력한다.

제한

  • 4 ≤ N ≤ 100
  • N은 4의 배수
  • 0 ≤ K ≤ 10
  • 1 ≤ 각 어항에 들어있는 물고기의 수 ≤ 10,000

예제 입력 1

8 7
5 2 3 14 9 2 11 8

예제 출력 1

1

예제 입력 2

8 4
5 2 3 14 9 2 11 8

예제 출력 2

2

정리를 두 번 하면 다음과 같아진다.

예제 입력 3

8 3
5 2 3 14 9 2 11 8

예제 출력 3

3

정리를 3번 하면 다음과 같다.

 

 

자는 해당 문제를 이해하는데 최대한 시간을 투자해서 문제를 풀었다.

어항이 변화하는 과정 하나하나를 천천히 구상하고 만들어가며 문제를 풀었는데

다행히 반복되는 과정이 있어 해당 부분은 함수로 구성해서 진행했다.

 

가장 먼저, 어항 최대 최소의 차가 k이하인 경우에 함수를 탈출하고

그게 아닌 경우에는 가장 작은 수의 어항에 한 마리씩 추가하는 과정을 진행하고

cnt + 1을 해준다.

# 값 비교해서 k보다 작거나 같으면 아웃
# 그게 아니면 가 장 작은 어항에 물고기 1씩 추가
ls_min, ls_max = min(ls), max(ls)
if ls_max - ls_min <= k: break
else:
    cnt += 1
    for idx in range(n):
        ls[idx] += 1 if ls[idx] == ls_min else 0

 

그 다음 어항을 회전 시키는데 공중 부양된 어항의 col길이가 가장 아랫단의 col이하일 때까지 회전을 진행한다.

코드를 보면 아래와 같다

# 공중부양 수행하는데 가장 아랫단의 어항보다
# 공중부양 어항의 길이가 길면 나온다
while True:
    length = len(bowls[0]) if bowls else 1
    tmp, remains = ls[:length], ls[length:]
    bowls.append(tmp)
    ls = remains[:]
    if bowls and len(bowls) > len(ls):
        bowls.pop()
        bowls.append(tmp + remains)
        break
    bowls = list(map(list, zip(*bowls[::-1])))

 

 

세번째로는 회전을 마친 어항의 상태에서 인접한 어항끼리 값을 비교해

5로 나눈 몫이 0보다 크면 그 값만큼 큰놈은 빼고 작은 놈은 더한다.

 

visited를 이용해 변화되는 값을 저장해준다.

이후 다 변환된 값을 boards에 더해주면 끝

def FeedFish(fishes):
    visited = [[0] * len(fish) for fish in fishes]
    for row in range(len(fishes)):
        for col in range(len(fishes[row])):
            for j, i in [[-1, 0], [0, 1], [1, 0], [0, -1]]:
                nj, ni = row + j, col + i
                if 0 <= nj < len(fishes) and 0 <= ni < len(fishes[nj]):
                    abs_val = (fishes[row][col] - fishes[nj][ni]) // 5
                    if abs_val > 0:
                        visited[nj][ni] += abs_val
                        visited[row][col] -= abs_val

    # 동시에 일어난 어항의 변화를 적용시켜줌
    for row in range(len(fishes)):
        for col in range(len(fishes[row])):
            fishes[row][col] += visited[row][col]

    return fishes

 

네 번째로는 위 과정을 끝낸 후,

한 줄로 만드는데 맨 아래 왼쪽부터 위로 올라가는 순서로 깔아준다.

이 부분이 헷갈리기 쉬운 부분이다

def MakeOneLine(boards):
    boards = [deque(board) for board in boards]
    tmp = []
    while len(tmp) != n:
        for row in range(len(boards) - 1, -1, -1):
            if boards[row]:
                tmp.append(boards[row].popleft())
    else:
        return tmp

 

이제 그림 9와 그림 10을 만들어 주는데

이건 처음부터 한 줄로 시작하는 거라 편하게 만들었다.

# 그림 9 만드는 법
lft, rgt = bowls[:n // 2][::-1], bowls[n // 2:]
bowls = [lft, rgt]

# 그림 10 만드는 법
tmp = deque([])
for row in range(2):
    tmp.appendleft(bowls[row][:n // 4][::-1])
    tmp.append(bowls[row][n // 4:])
bowls = list(tmp)

 

그러고 인전한 물고기와의 교환과 한줄 만들기를 수행하면 한 loop가 끝이 난다.

 

전체 코드를 작성하면

아래와 같다.

import sys
from collections import deque

input = sys.stdin.readline


def FeedFish(fishes):
    visited = [[0] * len(fish) for fish in fishes]
    for row in range(len(fishes)):
        for col in range(len(fishes[row])):
            for j, i in [[-1, 0], [0, 1], [1, 0], [0, -1]]:
                nj, ni = row + j, col + i
                if 0 <= nj < len(fishes) and 0 <= ni < len(fishes[nj]):
                    abs_val = (fishes[row][col] - fishes[nj][ni]) // 5
                    if abs_val > 0:
                        visited[nj][ni] += abs_val
                        visited[row][col] -= abs_val

    # 동시에 일어난 어항의 변화를 적용시켜줌
    for row in range(len(fishes)):
        for col in range(len(fishes[row])):
            fishes[row][col] += visited[row][col]

    return fishes


def MakeOneLine(boards):
    boards = [deque(board) for board in boards]
    tmp = []
    while len(tmp) != n:
        for row in range(len(boards) - 1, -1, -1):
            if boards[row]:
                tmp.append(boards[row].popleft())
    else:
        return tmp


n, k = map(int, input().split())
ls = list(map(int, input().split()))
cnt = 0

while True:
    bowls = []
    # 값 비교해서 k보다 작거나 같으면 아웃
    # 그게 아니면 가 장 작은 어항에 물고기 1씩 추가
    ls_min, ls_max = min(ls), max(ls)
    if ls_max - ls_min <= k: break
    else:
        cnt += 1
        for idx in range(n):
            ls[idx] += 1 if ls[idx] == ls_min else 0

    # 공중부양 수행하는데 가장 아랫단의 어항보다
    # 공중부양 어항의 길이가 길면 나온다
    while True:
        length = len(bowls[0]) if bowls else 1
        tmp, remains = ls[:length], ls[length:]
        bowls.append(tmp)
        ls = remains[:]
        if bowls and len(bowls) > len(ls):
            bowls.pop()
            bowls.append(tmp + remains)
            break
        bowls = list(map(list, zip(*bowls[::-1])))

    # 인접한 물고기 주고 받기
    bowls = FeedFish(bowls)

    # 한 줄로 만드는 행위
    bowls = MakeOneLine(bowls)

    # 그림 9 만드는 법
    lft, rgt = bowls[:n // 2][::-1], bowls[n // 2:]
    bowls = [lft, rgt]

    # 그림 10 만드는 법
    tmp = deque([])
    for row in range(2):
        tmp.appendleft(bowls[row][:n // 4][::-1])
        tmp.append(bowls[row][n // 4:])
    bowls = list(tmp)

    # 인접한 물고기에게 밥주는 행위
    bowls = FeedFish(bowls)

    # 한 줄로 만드는 행위
    ls = MakeOneLine(bowls)

print(cnt)

 

해당 글이 도움이 되셨다면,

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

'IT 톺아보기 > 알고리즘' 카테고리의 다른 글

백준 23288번 | 주사위 굴리기 2 - python  (1) 2022.10.13
백준 23290 | 마법사 상어와 복제 - python  (1) 2022.10.13
백준 16236번 | 아기 상어 - python  (0) 2022.10.07
백준 17142번 | 연구소 3 - python  (0) 2022.10.07
백준 23288번 | 주사위 굴리기 2 - python  (2) 2022.10.07

관련글

티스토리툴바