201. 못생긴 수

JUNGLE

• 못생긴 수란, 소인수분해 했을 경우 나오는 소인수가 2, 3 그리고 5뿐인 수를 이야기 하며, 이를 수열로 늘어놓으면 다음과 같다.

  1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

• 이는 처음나오는 10개의 못생긴 수이며, 편의상 1을 포함하도록 하자.

• 정수 n이 주어졌을 때, n번째 못생긴 수를 출력하는 프로그램을 작성하라.

  
  

• 입력조건

  • 한 줄에 양의 정수 n (n≤1,500)이 주어진다. 입력에 0 이 주어질 때까지 계속 한다.
  
  

• 출력조건

  • 출력에는 n번째 못생긴 수를 출력한다.

1. 다이나믹 프로그래밍

n = int(input())

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

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

for l in range(1, n):
  #가능한 곱셈 결과 중에서 가장 작은 수 선택
  ugly[l] = min(next2, next3, next5)
  if ugly[l] == next2:
    i2 += 1
    next2 = ugly[i2] * 2
    print('i2: ', i2)
    print('next2:', next2)
    print(ugly)
  if ugly[l] == next3:
    i3 += 1
    next3 = ugly[i3] * 3
    print('i3: ', i3)
    print('next3:', next3)
    print(ugly)
  
  if ugly[l] == next5:
    i5 += 1
    next5 = ugly[i5] * 5
    print('i5: ', i5)
    print('next5:', next5)
    print(ugly)
#n번째 못생긴 수 출력
print(ugly[n - 1])

print(ugly)

2. C++

#include <bits/stdc++.h>

using namespace std;

int n;
int ugly[1000]; // 못생긴 수를 담기 위한 테이블 (1차원 DP 테이블)

int main(void) {
    cin >> n;

    // 2배, 3배, 5배를 위한 인덱스
    int i2 = 0, i3 = 0, i5 = 0;
    // 처음에 곱셈 값을 초기화
    int next2 = 2, next3 = 3, next5 = 5;

    ugly[0] = 1; // 첫 번째 못생긴 수는 1
    // 1부터 n까지의 못생긴 수들을 찾기
    for (int l = 1; l < n; l++) {
        // 가능한 곱셈 결과 중에서 가장 작은 수를 선택
        ugly[l] = min(next2, min(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번째 못생긴 수를 출력
    cout << ugly[n - 1] << '\n';
}