[DP] 못생긴 수

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 24분

1. 문제 설명

- 인수가 2, 3, 5로만 구성된 수를 '못생긴 수'라고 한다. 1도 못생긴 수로 포함시킬 때, n이 입력으로 주어지면 n번째 못생긴 수를 출력한다.

2. 접근 방식

- 입력으로 들어오는 n의 수가 1000이하라고 해서, 1000이하면 2, 3, 5 원소들의 순열이 1000개 이상이 될 수 있게만 하면 되겠다고 생각을 했다.

- 그리고 소수를 구하는 기법인 '에라토스테네스의 체'기법을 활용하면 되겠다고 생각을 했다.

- 문제를 풀기는 했는데, 답을 제출해볼 수 있는 방법이 없어서 해답을 봤는데 해답에서는 또 다른 방법으로 접근했길래 같이 적어둔다.

3. 코드

- 내 방법(에라토스테네스의 체 이용)

n = int(input()) 
import math
ls = [False] * 4000
target = [2, 3, 5]
for i in range(2, int(math.sqrt(len(ls)))):
    if i in target:
        if ls[i] == False:
            ls[i] = True
            j = 2
            while (i*j) < len(ls):
                ls[i*j] = True
                j += 1
    else:
        if ls[i] == False:
            j = 2
            while (i*j) < len(ls):
                ls[i*j] = False
                j += 1
ls[1] = True
answer = []
for i, v in enumerate(ls):
    if v:
        answer.append(i)
print(answer[n-1])

- 해답 코드 (index를 하나씩 증가시키면서 값을 넣음)

n = int(input())

ugly = [0]* n
ugly[0] = 1
i2 = i3 = i5 = 0
next2, next3, next5 = 2, 3, 5 # 초기화

# 1부터 n까지의 못생긴 수 찾기
for l in range(1, n):
    # 가능한 곱셈 결과 중 가장 작은 수 선택
    ugly[l] = min(next2, next3, next5)
    if ugly[l]==next2:
        i2+=1
        next2 = ugly[i2]*2
    if ugly[l]==next3:
        i3+=1
        next3 = ugly[i3]*3
    if ugly[l]==next5:
        i5+=1
        next5 = ugly[i5]*5
        
print(ugly[n-1])

4. 코멘트

- for문이 더 적게 사용되기 때문에 해답 코드가 더 경제적인 건 맞는 것 같다.

- 하지만 나름대로 생각해서 문제를 해결했다는 점에서 조금이나마 위로가 된다. 

- 만약 문제를 제출할 수 있는 사이트가 있었다면 아마 내 코드는 시간초과 될 수 있었지 않을까 싶다.

- 해당 문제는 다시 한번 살펴볼 필요가 있다.