군대에서_코딩하기_알고리즘_20

오늘 풀었던 문제는 아니고, 한 2~3일에 걸쳐서 풀었던 문젠데(물론 사지방 연등시간에만) Ugly Numbers를 구하는 문제다.

• Ugly Numbers란?
  -> 어떤 수를 소인수분해 했을 때, 그 소인수가 2 또는 3 또는 5로만 이루어진 수를 Ugly Number라고 부른다.

예를 들어 Ugly Number를 차례대로 적어보면 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...가 있다
이때 N을 주어주면, N번째 Ugly Number를 구하는게 문제였다.

그냥 노가다로 하나 하나씩 다 나눠보면서 구해보는 방법도 있겠지만, 그렇게 할 경우 당연히 time_limited이 난다. 그래서 처음에 어떻게 풀어야할지 참 많은 고민을 했고, 결국에는 삼중 포인터로 접근해야한다는 것을 알았다.

p1, p2, p3를 포인터라 가정했을 때, 처음 초기값을 1로 잡고, 반복해서 2,3,5를 각각 p1 p2 p3에 곱해주면서 최솟값을 Nums라는 배열에 넣어주면 된다. 또한 최솟값을 구했을 경우, 포인터들의 값을 Nums 배열의 다음값으로 넘겨주면된다.
예를 들면 p1이 2였고 p1에 2를 곱한 값이 최소였을 경우, p1은 3이 된다. 이런식으로 포인터들의 값을 하나씩 옮겨주고, Nums 배열에 최소값을 하나씩 추가해주면 된다.
코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
    
    int N, i;
    int Nums[1501]={0,};
    Nums[1] = 1;
    int p1=1,p2=1,p3=1;
    int cnt1=1, cnt2=1, cnt3=1;
    int temp1, temp2, temp3, result;
    cin>>N;
    
    for(i=1; i<=N; i++){
        temp1 = p1*2;
        temp2 = p2*3;
        temp3 = p3*5;
        
        if((temp1<temp2)&&(temp1<temp3)){
            cnt1++;
            result = temp1;
            Nums[i+1] = result;
            p1 = Nums[cnt1];
        }
        else if((temp2<temp1)&&(temp2<temp3)){
            cnt2++;
            result = temp2;
            Nums[i+1] = result;
            p2 = Nums[cnt2];
        }
        else if((temp3<temp1)&&(temp3<temp2)){
            cnt3++;
            result = temp3;
            Nums[i+1] = result;
            p3 = Nums[cnt3];
        }
        else if((temp1==temp2)&&(temp2==temp3)){
            cnt1++;
            cnt2++;
            cnt3++;
            Nums[i+1] = temp1;
            p1 = Nums[cnt1];
            p2 = Nums[cnt2];
            p3 = Nums[cnt3];
        }
        
        else if(temp1==temp2){
            cnt1++;
            cnt2++;
            Nums[i+1] = temp1;
            p1 = Nums[cnt1];
            p2 = Nums[cnt2];
        }
        
        else if(temp2==temp3){
            cnt2++;
            cnt3++;
            Nums[i+1] = temp2;
            p2 = Nums[cnt2];
            p3 = Nums[cnt3];
        }
        
        else if(temp1==temp3){
            cnt1++;
            cnt3++;
            Nums[i+1] = temp1;
            p1 = Nums[cnt1];
            p3 = Nums[cnt3];
        }
    }
    
    cout<<Nums[N];
    
}

포인터들의 값이 같아질 경우 예외처리를 하느라 코드가 조금 지저분하고 길어졌는데, 조금 신경써서 작성하면 훨씬 깔끔하게 짤 수 있을것같다!