설탕 배달

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

2839번: 설탕 배달

 

나의 풀이

import sys
input = sys.stdin.readline

n = int(input().rstrip())
table = [float('inf')] * (n + 1)

table[3] = 1
table[4] = -1
table[5] = 1
table[6] = 2
table[7] = -1

if n <= 7:
    print(table[n])
else:
    for i in range(8, n+1):        
        for j in range(3, i):
            by_three, by_five = None, None
            if table[j] != -1 and (i - j) % 3 == 0:
                by_three = table[j] + ((i - j) // 3)                
            if table[j] != -1 and (i - j) % 5 == 0:
                by_five = table[j] + ((i - j) // 5)                
            
            if by_three != None and table[i] >= by_three:
                table[i] = by_three
            if by_five != None and table[i] >= by_five:
                table[i] = by_five
    print(table[n])

dp 방식으로 문제를 풀 수 있을 것 같아서 dp table을 이용하여 푸는 방식으로 코드를 짜보았다.

알고리즘은 맞는 것 같으나, 시간복잡도가 O(N^2)인 것이 문제였는지 시간 초과로 정답 처리는 받지 못했다.

물론 n이 될 수 있는 수의 범위가 3부터 5000까지로 매우 크지 않기 때문에 O(N^2)의 방식으로도 정답 처리를 받을 수 있을 것 같기는 하다. 그러나 나의 방식은 연산 시간이 더 걸리는 것 같다. 최악의 O(N^2)의 방식으로 코드를 짰기 때문에 시간 초과가 뜨지 않나라는 생각이다.

도대체 어떤 부분이 시간이 많이 걸리는 것인지, 그리고 어떻게 개선할 수 있을지 계속 찾아봐야겠다.

 

다른 사람의 풀이

import sys
input = sys.stdin.readline
n = int(input().rstrip())

result = -1

for i in range((n // 5), -1, -1):
    if (n - 5*i) % 3 == 0:
        result = i + (n - 5*i) // 3
        break
print(result)

다른 사람의 풀이를 찾아보니 너무나도 간단한 방식으로, 그리고 심지어는 dp table을 이용하지 않고도 문제를 풀어내고 있었다.

코드를 한 줄씩 따라 적어보면서 차근차근 이해해보니 나의 코드가 매우 부끄럽기도 했다.

3과 5는 서로소이기에 4와 7을 제외한 모든 수를 나타낼 수 있다는 것을 확실히 알고 있다면 짤 수 있는 코드라고 생각됐다.

특히 break를 걸어줌으로써 min의 경우의 수만을 저장시키는 것을 보고 더 열심히 공부해야겠다는 생각이 들었다.

 

느낀점

나의 약점인 dp 문제를 더 많이 풀어봐야겠다. 그리고 충분히 이 문제를 그리디 알고리즘으로 볼 수도 있었지만, 그렇게 풀어내지 못한 나를 반성한다.