23291번 - 어항 정리

문제

23291번: 어항 정리 (acmicpc.net)

23291번: 어항 정리

풀이

요구사항이 꽤 많은데, 차근차근 정리하며 구현하는것이 중요하다.

어항에 물고기 넣기

가장 물고기 숫자가 적은 어항에 물고기를 한마리 씩 넣어야 하므로, 어항 일차원 리스트를 정렬한 뒤 upper bound로 물고기를 넣어줘야하는 어항 인덱스를 찾았다.

공중부양 쌓기 1

맨 왼쪽 어항을 그 옆에있는 어항위에 쌓은 뒤, 조건에 따라 어항을 쌓아간다. 왼쪽에 몰려있는 두개 이상 쌓여있는 어항들을 빼서 90도 돌린뒤 놓여있는 어항들에 올리는 것이므로, 전체를 큐로 보고, 각 어항이 쌓이는 열을 리스트로 보았다. 90도 돌리는것은, 큐안의 리스트에 요소들을 추가해줄 것이므로 행렬을 전치해서 가져왔다. 말이 복잡하지만, 결국 전체를 큐로 보고 풀었다는 사실이 핵심이다.

공중부양 쌓기 2

N은 4의 배수로 주어지며 어항의 전체개수는 변하지 않는다는 사실을 기억하면 된다. 절반을 떼어서 반전시킨뒤 스택에 쌓는다고 생각하면 된다.

물고기 수 조절

온풍기 안녕! 문제에서 온도조절한 것과 비슷하게 풀이하면 된다.

일렬로 늘어놓기

탐색 순서를 유의하자.

import math
from collections import deque

N,K = map(int,input().split())
fishbowls = list(map(int,input().split()))

h_dp = list(map(lambda x : math.ceil(x/2) + 1, range(1,101)))
w_dp = list(map(lambda x : math.ceil(x/2) + 1, range(100)))
dRow = [-1,0,1,0]
dCol = [0,-1,0,1]


def upper_bound(li,target):
    start,end = 0,len(li)
    while start < end:
        mid = (start + end) // 2
        if target >= li[mid][0]:
            start = mid + 1
        else:
            end = mid
    return end - 1


def check():
    temp = sorted(fishbowls)
    return True if temp[-1]-temp[0] <= K else False


answer = 0

while True:
    if check():
        break
    # 가장 물고기가 적은 어항들에 물고기 넣기
    temp = sorted(map(lambda x : (x[1],x[0]), enumerate(fishbowls)))
    end = upper_bound(temp,temp[0][0])
    for i in range(end+1):
        fishbowls[temp[i][1]] += 1
    # 어항 쌓기
    liq = deque([[elem] for elem in fishbowls])
    bowl = liq.popleft()
    liq[0] += bowl
    # 공중부양 쌓기 1
    for i in range(100):
        if h_dp[i] > len(liq)-w_dp[i]:
            break
        mat = []
        for _ in range(w_dp[i]-1,-1,-1):
            mat.append(liq.popleft())
        # 90도 회전 후 쌓기
        for idx,val in enumerate(map(lambda x : list(reversed(x)),zip(*mat))):
            liq[idx] += val
    w,h = len(liq),len(liq[0])
    for i in range(w):
        while len(liq[i]) < h:
            liq[i].append(0)
    # 물고기 수 조절
    new_liq = [[*elem] for elem in liq]
    for row in range(w):
        for col in range(h):
            if liq[row][col] > 0:
                for j in range(4):
                    nRow,nCol = row+dRow[j],col+dCol[j]
                    if 0 <= nRow < w and 0 <= nCol < h and liq[nRow][nCol] > 0:
                        d = (liq[row][col] - liq[nRow][nCol]) // 5
                        if d > 0:
                            new_liq[row][col] -= d
                            new_liq[nRow][nCol] += d
    # 일렬로 늘어놓기
    fishbowls = []
    for li in new_liq:
        for e in li:
            if e == 0:
                break
            fishbowls.append(e)
    # 공중부양 쌓기 2
    stack = [[*fishbowls]]
    for i in range(1,3):
        left,right = [],[]
        for row in range(2**(i-1)):
            left.append(stack[2**(i-1)-row-1][N//i//2-1::-1])
            right.append(stack[row][N//i//2::])
        stack = left+right
    # 물고기 수 조절
    w,h = len(stack),len(stack[0])
    new_stack = [[*elem] for elem in stack]
    for row in range(w):
        for col in range(h):
            for i in range(4):
                nRow,nCol = row+dRow[i],col+dCol[i]
                if 0 <= nRow < w and 0 <= nCol < h:
                    d = (stack[row][col] - stack[nRow][nCol]) // 5
                    if d > 0:
                        new_stack[row][col] -= d
                        new_stack[nRow][nCol] += d
    # 일렬로 늘어놓기
    fishbowls = []
    for col in range(h):
        for row in range(w-1,-1,-1):
            fishbowls.append(new_stack[row][col])
    answer += 1

print(answer)