[Jungol] 1318 못생긴 수
DP
항상 문제를 풀다보면 sub problem의 중복 문제를 찾고 그것을 해소하기 위해 dp table이나 메모이제이션을 사용하는 방향으로 DP 생각이 나서 풀게 된다. 그래서 어찌 보면 DFS랑 되게 유사하게 생각의 사고를 시작하게 되는 것 같다.
이 문제는 2, 3, 5만 소인수로 갖는 N 번째 숫자를 반복해서 찾아야 하는 문제이다. 딱봐도 중복 문제가 엄청 나오게 생겼다. 그래서 DP를 고려하기 시작했다.
이런식으로 중복 문제가 발생하고 이를 메모이제이션 해야 시간복잡도를 줄일 수 있음을 알 수 있다.
다만 여기서는 해당 숫자가 등장했는지만 알아보면 되므로, set 자료구조를 사용하여 skip 하는 식으로 구현하면 된다.
그리고, N 번쨰 오름차순으로 하나씩 세어줘야 하므로 min-heap을 사용해서 가장 최소값을 계속 pop할 수 있도록 구현한다.
- 초기에 1은 넣어놓고, 2, 3, 5를 min-heap, set 자료구조에 넣는다.
- 하나 pop 해서 결과 리스트에 넣고, x2, x3, x5 한 값을 min-heap, set 자료구조에 넣는다.
- 만약 x2, x3, x5한 값이 set 자료구조에 있다면 min-heap에는 넣지 않는다.
- 최대 1500번 째 수를 반환해야 하므로 10억까지 반복한다.
- 입력이 주어지는대로 미리 계산한 결과 리스트에서 값을 하나씩 출력한다.
코드는 다음과 같다.
구현
import sys
import heapq
def solution(m):
calc = [2, 3, 5]
heap = []
for c in calc:
heapq.heappush(heap, c)
c_set.add(c)
cur = 0
while cur <= m:
cur = heapq.heappop(heap)
cache.append(cur)
for dc in calc:
if cur * dc in c_set:
continue
heapq.heappush(heap, cur * dc)
c_set.add(cur * dc)
if __name__ == "__main__":
cache = [1]
c_set = {1}
MAX = int(1e9)
solution(MAX)
while True:
N = int(sys.stdin.readline().rstrip())
if N == 0:
break
print(cache[N-1]) # N번째 못생긴 수