✅이코테 - Ch16. 못생긴 수 (DP)

문제 출처 : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=597&sca=30 

JUNGOL

 

 

#1. 개선할 점

 

- 완전탐색을 생각했을 때 경우의 수가 너무 많아서 dp를 생각했지만,

점화식을 세우려고 하니까 쉽지 않았다.

 

- 못생긴 수에 2, 3, 5를 곱한 수 또한 못생긴 수이므로,

1에서부터 시작해서 차근 차근 못생긴 수를 구해나가는 방법을 사용하면 생각보다 간단히 풀 수 있었다.

 

Ex)

i = 1) 못생긴 수 = [1]

1*2

1*3

1*5 추가

 

i = 2) 못생긴 수 = [1, 2, 3, 5]

2*2

2*3

2*5

 

i=3) 못생긴 수 = [1, 2, 3, 4, 5 6, 10]

…

반복

 

 

점화식을 세우기 힘들때는 왼쪽에서부터 (어떤 기준으로부터) bottom-up 방식으로 채워나가보자.

 

[책 풀이]

# 못생긴 수

'''
입력) n (1이상 1000이하)
출력) n번째 못생긴 수 출력

- 못생긴 수란 2, 3, 5를 약수로 가지는 합성수

1은 못생긴수임

'''

n = int(input())

ugly = [0] * n # 못생긴 수를 담기위한 dp 테이블
ugly[0] = 1 # 첫번째 못생긴 수는 1

# 2배, 3배, 5배를 위한 인덱스
i2 = i3 = i5 = 0

# 처음 곱셈 값을 초기화
next2, next3, next = 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

# n번째 못생긴 수를 출력
print(ugly[n-1])

 

 

#3. 다시 풀기

 

책 풀이처럼 풀 수 있을지 확신이 안서서 다른 방식으로 풀어보았다.

 

# 못생긴 수

'''
입력) n (1이상 1000이하)
출력) n번째 못생긴 수 출력

- 못생긴 수란 2, 3, 5를 약수로 가지는 합성수

1은 못생긴수임

# 설계

1. 길이가 n인 dp테이블 만들기 dp[0] = 1
2. 못생긴 수 집합에 2, 3, 5넣기 -> {2, 3, 5}
3. 1부터 n-1까지 다음 방식으로 반복

    - 집합에서 가장 작은 수를 빼고 dp에 대입
    - 뺀 가장 작은 수의 2, 3, 5의 배수를 집합에 넣기
4. dp[n-1]을 출력

'''

n = int(input())
dp = [0] * n
dp[0] = 1

ugly = {2, 3, 5}

for i in range(1, n) :
    min_val = min(ugly)
    dp[i] = min_val

    ugly.remove(min_val)
    ugly.add(min_val * 2)
    ugly.add(min_val * 3)
    ugly.add(min_val * 5)

print(dp[n-1])