다시 봐야할 중요한 문제들

최소 동전, DP

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

import sys

input = sys.stdin.readline

def solution():
    n, k = map(int, input().split())
    dp = [0]*(k+1)
    coin = set()
    queue = []
    for _ in range(n):
        c = int(input())
        if c <= k:
            coin.add(c)
            queue.append((c, 2))
            dp[c] = 1
    coin = sorted(coin)
    while queue:
        i, cnt = queue.pop(0)
        if i == k:
            break
        for c in coin:
            if i+c > k:
                break
            if dp[i+c] == 0:
                dp[i+c] = cnt
                queue.append((i+c, cnt+1))
    print(dp[k] if dp[k] else -1)

solution()

내 코드

import sys
# sys.stdin = open('./dp/input_05.txt')
input = sys.stdin.readline

# input
N, M = map(int, input().split())
coins = set()
for _ in range(N):
    coin = int(input().rstrip())
    if coin <= M:
        coins.add(coin)

# dp list
dp = [0] * (M+1)
for coin in coins:
    dp[coin] += 1

# bottom-up
for i in range(1, M+1):
    tmp = 10001
    for coin in coins:
        if dp[i]:
            continue
        if i-coin > 0 and dp[i-coin]:
            tmp = min(dp[i-coin], tmp)
    dp[i] = tmp + 1 if tmp != 10001 else dp[i]
# print(*dp, sep=' ')
print(dp[M] if dp[M] else -1)

배울 점

• 큐를 이용해서 dp table(list)이 각 인덱스에 저장되는 카운트가 최소가 되도록 보장하였다.

하노이, Divide and Conquer

def hanoi(num, start, dest, extra):
    # base
    if num == 1:
        hanoi.count += 1
        print(f'a disk is moved from {start} into {dest}')
        return
    
    # general
    hanoi(num-1, start, extra, dest)
    hanoi.count += 1
    print(f'a disk is moved from {start} into {dest}')
    hanoi(num-1, extra, dest, start)


hanoi.count = 0
hanoi(
    num=3,
    start=1,
    dest=3,
    extra=2
)
print(hanoi.count)

치킨집 줄이기

from itertools import combinations
import sys
sys.stdin = open('./implementation/input_bj_15686.txt')
input = sys.stdin.readline

# input
N, M = map(int, input().split())
# graph = [list(map(int, input().rstrip().split())) for _ in range(N)] # '0' is empty, '1' is house, '2' is fried chicken joint
graph = []
houses, chick_place = [], []
for i in range(N):
    tmp = list(map(int, input().rstrip().split()))
    graph.append(tmp)
    for idx, j in enumerate(tmp):
        if j == 2:
            chick_place.append((i, idx))
        elif j == 1:
            houses.append((i, idx))
# print(*graph, sep='\n')
# print(*chick_place, sep='\n')

# list of each houses which includes distance of fried chicken places
dist_list = [[] for _ in range(len(houses))]
for idx, house in enumerate(houses):
    for chick in chick_place:
        dist = abs(chick[0] - house[0]) + abs(chick[1] - house[1])
        dist_list[idx].append(dist)
# print(*dist_list, sep='\n')

cases = list(combinations(range(len(chick_place)), M))
total = [0 for _ in range(len(cases))]
for case_idx, case in enumerate(cases):    
    for dist in dist_list:
        mn = 999999
        for i in case:
            mn = min(mn, dist[i])
        total[case_idx] += mn

print(min(total))

# 15686번 치킨 배달
# 브루트포스, 백트래킹
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
graph = [list(map(int, input().rstrip().split())) for _ in range(N)]
chicken_house = []
houses = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 2:
            chicken_house.append((i, j))
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            house_dist = []
            for row, col in chicken_house:
                house_dist.append(abs(row-i) + abs(col-j))
            houses.append(house_dist)

check = [0 for _ in range(len(chicken_house))]
def chicken_distance():
    indexs = []
    for i in range(len(chicken_house)):
        if check[i]:
            indexs.append(i)
    total = 0
    for house in houses:
        min_val = house[indexs[0]]
        for idx in indexs:
            if house[idx] < min_val:
                min_val = house[idx]
        total += min_val
    return total

min_chicken_dist = sys.maxsize
def Backtrack(start, chosen):
    global min_chicken_dist
    if chosen == M:
        k = chicken_distance()
        if k < min_chicken_dist:
            min_chicken_dist = k
    for i in range(start, len(chicken_house)):
        if check[i] == 0:
            check[i] = 1
            Backtrack(i, chosen+1)
            check[i] = 0

Backtrack(0, 0)

print(min_chicken_dist)

회고

itertools, combination으로 backtracking을 진행하였지만 아래 답안의 경우 recursion으로 작성했다. 실행시간에서 유의미한 차이를 보였고, 아래 답안의 backtracking은 어느정도 정형화되어 있다고 볼 수 있어서 익혀둘 필요가 있다.

캠핑

백준 4796

j=0
for i in[*open(0)][:-1]:
    j+=1
    L,P,V=map(int,i.split())
    x=0
    while V>0:
        x+=min(L,V)
        V-=P
    print(f"Case {j}: {x}")

open(0)은 sys.stdin 의미

터미널 상에서 EOF(end of file)값을 전하기 위해서는 cmd + d