알고리즘 :: 이것이 코딩 테스트다 :: DP :: Q35 :: 못생긴 수

문제

못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미한다. 1은 못생긴 수라고 가정한다. 이때 n번째 못생긴 수를 찾는 프로그램을 작성하시오.

문제접근

• 핵심은 못생긴 수에 어떤 수를 곱한 수는 못생긴 수라는 것이다.
• 1부터 시작해서 2, 3, 5를 곱한 수를 못생긴 수 배열에 넣으면 된다.
• 첫 번쨰 난관은 어떻게 숫자를 크기 순으로 넣을까? 라는 것이다.
  1. priority_queue를 이용하는 방법
     • heap을 사용하면 정렬을 유지하면서 자료를 넣을 수 있다.
     • 못생긴 수의 중복도 해결할 수 있다.
     • 다소 느리지만 확실한 방법이다.
  2. deque를 이용하는 방법.
     • 2, 3, 5의 못생긴 수의 배수를 저장할 외부 deque 공간을 만든다.
     • 반복문을 돌면서 각 deque의 front()를 비교해서 가장 작은 못생긴 수를 찾고 pop_front()해준 뒤 못생긴 수 배열에 넣는다.
     • 못생긴 수의 중복은 따로 해결해줘야 한다.

코드

#include <iostream>
#include <deque>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n;  cin >> n;
    
    int memo[1000] = {1, };	// i번째 못생긴 수 저장 공간.
    deque<int> two, three, five;
    for (int i = 1; i < n; ++i) {	// 한 번에 하나씩 저장해야 하는 게 핵심!
        two.push_back(memo[i - 1] * 2);		// 못생긴 수의 2의 배수 저장
        three.push_back(memo[i - 1] * 3);	// 못생긴 수의 3의 배수 저장
        five.push_back(memo[i - 1] * 5);	// 못생긴 수의 5의 배수 저장
		
	// 계산한 세 값중 최소값을 저장하고 deque에서 제거해준다. (중복값도 제거)
        int pushVar = min(min(two.front(), three.front()), five.front());
        memo[i] = pushVar;
        if (pushVar == two.front())	two.pop_front();
        if (pushVar == three.front())	three.pop_front();
        if (pushVar == five.front())	five.pop_front(); 
    }
	// 배열 인덱스 특징 때문에 n번째 못생긴 수는 n-1번째 인덱스에 저장됨.
    cout << memo[n - 1] << '\n';
}