Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 n번째 못생긴 수(Ugly Number) 구하기: 다이내믹 프로그래밍 완벽 가이드

못생긴 수(Ugly Number)란 소인수가 오직 2, 3, 5뿐인 양의 정수를 의미합니다. 처음 몇 개의 못생긴 수는 1, 2, 3, 4, 5, 6, 8, 9, 10, 12이며, 이 순서에서 10번째 못생긴 수는 12입니다.

이 문제는 n번째 못생긴 수를 효율적으로 찾는 것입니다. 모든 수를 하나씩 검사하는 브루트포스 방식은 매우 비효율적이지만, 다이내믹 프로그래밍(DP)과 세 개의 포인터를 활용하면 O(n) 시간 복잡도로 빠르게 해결할 수 있습니다.

알고리즘 핵심 아이디어

모든 못생긴 수는 이미 구한 더 작은 못생긴 수에 2, 3, 또는 5를 곱한 값입니다. 따라서 세 개의 후보 값을 유지하면서 그중 최솟값을 차례대로 배열에 채워 나가면 됩니다.

해결 단계

  • 크기가 n + 1인 배열 v를 생성합니다.

  • n이 1이면 1을 반환합니다.

  • two := 2, three := 3, five := 5로 초기화하고, 각 인덱스 twoIdx, threeIdx, fiveIdx도 2로 설정합니다.

  • i를 2부터 n까지 반복합니다.

    • curr := two, three, five 중 최솟값

    • v[i] := curr

    • curr == two라면 two := v[twoIdx] * 2로 갱신하고 twoIdx를 1 증가

    • curr == three라면 three := v[threeIdx] * 3으로 갱신하고 threeIdx를 1 증가

    • curr == five라면 five := v[fiveIdx] * 5로 갱신하고 fiveIdx를 1 증가

  • v[n]을 반환합니다.

C++ 구현 예제

아래 코드를 통해 동작 원리를 더 명확하게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int nthUglyNumber(int n) {
        vector <int> v(n + 1);
        if(n == 1){
            return 1;
        }
        int two = 2, three = 3, five = 5;
        int twoIdx = 2;
        int threeIdx = 2;
        int fiveIdx = 2;
        for(int i = 2; i <= n; i++){
            int curr = min({two, three, five});
            v[i] = curr;
            if(curr == two){
                two = v[twoIdx] * 2;
                twoIdx++;
            }
            if(curr == three){
                three = v[threeIdx] * 3;
                threeIdx++;
            }
            if(curr == five){
                five = v[fiveIdx] * 5;
                fiveIdx++;
            }
        }
        return v[n];
    }
};
main(){
    Solution ob;
    cout << (ob.nthUglyNumber(10));
}

입력

10

출력

12