[백준]230210-12 문제풀이

1463. 1로 만들기

N = int(input())
dic = {1: 0}
def mini(n):
    if n in dic.keys():
        return dic[n]
    else:
        if not n % 3 and not n % 2:
            dic[n] = min(mini(n//3) + 1, mini(n//2) + 1)
        elif not n % 3:
            dic[n] = min(mini(n//3) + 1, mini(n - 1) + 1)
        elif not n % 2:
            dic[n] = min(mini(n//2) + 1, mini(n - 1) + 1)
        else:
            dic[n] = mini(n - 1) + 1
        return dic[n]

print(mini(N))

드디어 먹어본 그 유명한 DP. 잘못된 재귀로 recursion error의 폭격을 맞았으나 그 덕분에 bottomup 방식도 배울 수 있었다.

9465. 스티커

T = int(input())
for i in range(T):
    n = int(input())
    # 스티커 입력
    d = []
    for j in range(2):
        d.append(list(map(int, input().split())))
    # n = 1 edgecase
    if n == 1:
        print(max(d[0][0], d[1][0]))
    # 각 스티커 선택 시 최대값 누적 저장할 리스트 생성
    else:
        maxi = [[0] * n for _ in range(2)]
        for j in range(2):
            for k in range(2):
                maxi[j][k] = d[j][k]
        maxi[0][1] += maxi[1][0]
        maxi[1][1] += maxi[0][0]
        # 최대값 갱신
        for j in range(2, n):
            maxi[0][j] = max(d[0][j] + maxi[0][j-2], d[0][j] + maxi[1][j-1], d[0][j] + maxi[1][j-2])
            maxi[1][j] = max(d[1][j] + maxi[1][j-2], d[1][j] + maxi[0][j-1], d[1][j] + maxi[0][j-2])
        # 출력
        print(max(maxi[0][n-1], maxi[0][n-2], maxi[1][n-1], maxi[1][n-2]))

이전에 호기롭게 도전했다가 개박살났던 문제. DP 문제를 볼 때 대충 어떤 식으로 점화식을 세우는지 감을 잡아보기에 좋았다. 근데 애초에 점화식을 잘 세워야 개고생하지 않는다는 교훈을 준 문제...

2164. 카드 2

import sys
from collections import deque

n = int(sys.stdin.readline())
deq = deque(i+1 for i in range(n))

while deq:
    a = deq.popleft()
    deq.rotate(-1)

print(a)

주말이라 가벼운 마음으로 틀렸던 문제 리벤지... 라이브러리의 중요성을 깨달은 상태라 deque 라이브러리 찾아서 한번 연습해봤다.

7662. 이중 우선순위 큐

import heapq
import sys

T = int(sys.stdin.readline())
for i in range(T):
    heap1 = []
    heap2 = []
    n = int(sys.stdin.readline())
    icount = dcount = 0
    visited = [False] * n
    for j in range(n):
        com = sys.stdin.readline().split()
        if com[0] == 'I':
            icount += 1
            heapq.heappush(heap1, (int(com[1]), j))
            heapq.heappush(heap2, (-int(com[1]), j))
            visited[j] = True
        elif com[0] == 'D':
            if dcount < icount:
                dcount += 1
                if com[1] == '-1':
                    while heap1 and not visited[heap1[0][1]]:
                        heapq.heappop(heap1)
                    if heap1:
                        visited[heap1[0][1]] = False
                        heapq.heappop(heap1)
                elif com[1] == '1':
                    while heap2 and not visited[heap2[0][1]]:
                        heapq.heappop(heap2)
                    if heap2:
                        visited[heap2[0][1]] = False
                        heapq.heappop(heap2)
    while heap1 and not visited[heap1[0][1]]:
        heapq.heappop(heap1)
    while heap2 and not visited[heap2[0][1]]:
        heapq.heappop(heap2)

    if heap1:
        print(-heap2[0][0], heap1[0][0])
    else:
        print('EMPTY')

문제는 매우 단순하지만, minheap과 maxheap을 다룰 때 같은 값을 어떻게 처리할지가 관건이다. 두 힙을 만들어놓고 push랑 pop 횟수만 계산해서 풀어보려고도 했는데 반례에서 자꾸 걸렸다. 반례를 댈 순 없었지만 어렴풋이 힙 관리가 제대로 안되기 때문이라는 감이 잡혔다. 그래도 힙을 훑지 않고 어케 같은 값을 찾을지... heapq를 쓰면서 종단에 어떻게 최소최대값을 넣어둘지가 도저히 생각이 안나서 결국 구글링했다. 그래프에서 쓰던 visited를 이용해 해당 값의 진정한 값이 나올때까지 허수를 제거하는 방식을 쓰는 것이었다. 혼자서는 절대 생각 못했을 듯... 이런식으로 노하우 하나하나씩 배워가면서 어려운 문제를 풀 내공이 생기는가보다 ㅠ