[실버 I] 13910번. 개업

 문제 

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

13910번: 개업

 사용 언어 

Python3

 풀이 과정 

일단 푼 시간도 진짜 오래 걸렸는데 푸는 과정에서 문제를 잘못 봐서 두 번이나 함정에 빠졌다...

1. 해빈이는 양손잡이이기 때문에 한 번에 두 개의 웍만 사용할 수 있다.
2. 정확한 짜장면의 수만큼 요리할 수 있는 경우가 없을 경우 -1 출력

나는 1번을 안 보고 아래와 같이 모든 조합의 합을 구했고 당연히 이중 for문으로 시간이 오래 걸릴 수밖에 없었다.

내가 생각해도 경우가 너무 많은데 문제가 그걸 원하면 해줘야지 했던...

근데 역시나 2개씩 조합만 구하면 되는거였잖아!!!

# 한 번의 요리로 만들 수 있는 모든 noodle 개수 집합
wokCombi = set()
for i in range(1, len(wokSize)+1):
    combi = combinations(wokSize, i)
    for j in combi:
        wokCombi.add(sum(j))

그리고 2번 조건을 안봐서 시간 초과나서 코드 수정하다가 중간에 깨닫고 추가해줬다.
그래도 위안이 되는 점은 코드를 짜면서 내가 이거 답이 안나오는 경우도 있을 것 같은데..? 라는 생각을 했다는거?ㅋㅋㅋ
암튼 실버 I 레벨 문제도 아주 힘겹게 풀었다😢

PyPy3 웬만하면 안 쓰려고 하는데 쓰고도 채점 퍼센트가 1%씩 힘겹게 올라가길래 두근거리면서 본 맞았습니다!!

어쨌든 문제를 꼼꼼이 읽어야 한다.

 제출 답안 

# 최소 몇 번의 요리로 주문을 처리할 수 있는지
from sys import stdin
from itertools import combinations

noodle, wok = map(int, stdin.readline().split())
wokSize = list(map(int, stdin.readline().split()))

# 양손잡이가 한 번의 요리로 만들 수 있는 모든 noodle 개수 집합
wokCombi = set(wokSize)
combi = combinations(wokSize, 2)
for j in combi:
    wokCombi.add(sum(j))

dp = [0] * (noodle + 1)
# wokCombi에서 몇 번을 더해야 noodle 개수가 될지 동적계획법
if noodle in wokCombi:
    print(1)
else:
    for i in range(1, len(dp)): # 1 ~ 6
        minVal = float("inf")
        for x in wokCombi: # 1, 3, 4
            if (i-x >= 0):
                minVal = min(minVal, dp[i-x] + 1)
        dp[i] = minVal
    print(-1 if dp[-1] == float("inf") else dp[-1])

 공부한 내용 

무한히 큰 수

코딩 테스트 문제 등을 풀다 보면, 최솟값을 저장하는 변수에 아주 큰 값을 할당해야 할 때가 있다.

그럴 때 사용하기 좋은  inf 에 대해 알아보자.

min_val = float('inf')
min_val > 10000000000

위와 같이 어떤 숫자와 비교해도 무조건 크다고 판정된다.

따라서 코딩테스트 문제를 풀면서 이번 문제와 같이 최솟값을 비교할 때 기본값을 float("inf")로 설정해두고 새로운 값이 있다면 비교하는 방식으로 사용하기 좋은 것 같다.

 

추가로  inf 에는 음수 기호를 붙이는 것도 가능하다.

그러니까 반대로 최댓값을 비교할 때 사용하면 좋을 것이다. 보통 0과 비교하지만 비교해야 할 숫자에 음수도 있을 때는 사용하게 될 것 같다.

max_val = float('-inf')

 

출처: https://programmers.co.kr/learn/courses/4008/lessons/52865

 다른 사람 답안 

이제 나는 약간 결론을 내린게 대부분의 동적 계획법 문제는 bfs로도 풀 수 있고
항상 bfs가 더 시간복잡도가 좋다는 것이다.

아니 열심히 동적 계획법 공부해놨더니 bfs가 더 좋아...? 약간 억울하긴 한데😂
어차피 bfs도 다시 공부할거였으니까... 내일부턴 다시 bfs 문제를 도전해야겠다.

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

st = set()
for i in range(m):
    st.add(li[i])
    for j in range(i + 1, m):
        st.add(li[i] + li[j])

dp = [-1] * (n + 1)
dp[0] = 0

for value in st:
    for i in range(n - value + 1):
        if dp[i] != -1:
            v = i + value
            if dp[v] == -1 or dp[v] > dp[i] + 1:
                dp[v] = dp[i] + 1

print(dp[-1])

출처: 백준 채점 현황

import sys
input = sys.stdin.readline
from collections import deque

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

cases = set()
visited = [0]*(n+1)

for i in range(m):
    if woks[i] > n :
        break
    cases.add(woks[i])
    visited[woks[i]] = 1
    for j in range(i):
        if woks[i]+woks[j] > n:
            break
        cases.add(woks[i]+woks[j])
        visited[woks[i]+woks[j]] = 1
        
cases = sorted(cases)

q = deque(cases)

while q:
    now = q.popleft()
    
    if now == n:
        break
        
    for case in cases:
        if now + case <= n and not visited[now+case]:
            visited[now+case] = visited[now]+1
            q.append(now+case)

print(-1 if not visited[n] else visited[n])

 

출처: 백준 채점 현황

 

코드 공개된 것 중 가장 빠른 시간복잡도와 이해하기 쉬워보이는 버전 두 개를 골랐다.

그래도 대부분의 사람들이 이 문제는 Python3가 아닌 PyPy3로 해결한 걸 보면 역시 시간이 좀 걸리는 문제였던걸로...

(Python3로 성공하신 분 딱 두 분 있는데 소요 시간이 각각 3596ms, 4452ms 였다 ㄷㄷ)

 

근데 첫 번째 코드를 보며 알았는데 처음에 dp를 초기화할 때 -1로 하면 마지막 삼항연산자를 뺄 수 있다는 것!!

내 코드에서는 inf와 비교해야 해서 -1이 남아있을 수 없었다... 시간 줄어드나 고쳐봤다가 괜히 두 번 더 틀림 ㅎㅎ

역시...다이아몬드는 다르다 달라