처음 문제를 보고 구현하는 방법이 그대로 적혀있길래 쓰인대로 구현해서 통과했었는데,
1. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
이 부분을 가장 짧은걸 자르라길래 우선순위 큐를 이용해서 구현했었습니다
import heapq
target = int(input())
heap = [64]
while sum(heap) != target:
splited = heapq.heappop(heap) // 2
if splited < 1: continue
heapq.heappush(heap, splited)
if not target < sum(heap): heapq.heappush(heap, splited)
print(len(heap))
그래서 이렇게 코드를 짜서 통과했는데 코드를 보니까 어차피 힙에 새로 추가되는건 잘린 막대이기 때문에 무조건 최소값이라 우선순위 큐를 쓸 필요가 없더라고요
target = int(input())
stack = [64]
while sum(stack) != target:
splited = stack.pop() // 2
if splited < 1: continue
stack.append(splited)
if not target < sum(stack): stack.append(splited)
print(len(stack))
우선순위가 필요 없단걸 알게 된 후에 바로 기본 스택을 이용하는식으로 코드를 고쳤어요
코드를 고치고 나니 메모리 사용량도 조금 줄었고 시간이랑 코드 길이도 조금씩 준걸 볼수 있었습니다!
'알고리즘 > 백준' 카테고리의 다른 글
백준 2644번 촌수계산 파이썬 풀이 (0) | 2021.03.19 |
---|---|
백준 1292번 쉽게 푸는 문제 파이썬 풀이 (0) | 2021.03.12 |
백준 5585번 거스름돈 C#풀이 (0) | 2019.12.14 |