[Python/파이썬] 백준 13902번 개업 2

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

코드

import sys
input = sys.stdin.readline

INF = int(1e9)

n, m = map(int, input().split())
s = list(map(int, input().split()))

wok_set = set(s)
dp = [INF]*(n+1)
for i in range(m):
    dp[s[i]] = 1
    for j in range(i+1, m):
        if s[i]+s[j] <= n:
            wok_set.add(s[i]+s[j])
            dp[s[i]+s[j]] = 1

for i in range(1, n+1):
    if dp[i] == 1:
        continue
    for ws in wok_set:
        if i-ws < 0 or dp[i-ws] == INF:
            continue
        dp[i] = min(dp[i], dp[i-ws]+1)

print(dp[n] if dp[n] != INF else -1)

 

로직은 어렵지 않은데 시간 복잡도 줄이기가 정말 어려웠던 문제였다...

조건문을 잘 사용해서 필요없는 연산은 최대한 넘어가는 것이 중요하다.

 

1. 웍으로 한 번에 조리 가능한 경우의 수를 wok_set에 저장할 때 dp에도 1로 표시해주기

dp[i]에는 i개의 짜장면을 조리하는 최소의 경우의 수가 저장된다. 그렇기 때문에 웍으로 한 번에 조리가 가능한 수를 wok_set에 저장할 때 dp에도 1이라고 표시를 해뒀다가 나중에 dp를 계산할 때 이미 dp[i] == 1인 i는 continue해주면 불필요한 연산을 줄일 수 있다.

 

2. `dp[i-ws]`가 INF인 경우는 연산하지 않고 넘어가기

`dp[i-ws]`가 INF이라는 것은 i-ws 그릇은 만들 방법이 없다는 뜻이다. 그렇기 때문에 여기서 한 번 더 조리를 해서 i개의 짜장면을 만들 수 있는지는 고려하지 않아도 된다. continue하자.