✍️Today I Learned

📅 2025-07-26

• 프로그래머스 - 숫자 변환하기

프로그래머스 - 숫자 변환하기

문제링크

문제 설명
자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.
x + n
x * 2
x * 3
자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항
1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y

처음 풀이(시간초과)

재귀로 풀었지만 시간초과 발생

#include <vector>
#include <algorithm>

using namespace std;

int cal(int x, const int& y, const int& n, int count)
{
    if (x > y) return -1;
    if (x == y) return count;

    vector<int> result;

    int temp = cal(x + n, y, n, count+1);
    if (temp > -1) result.push_back(temp);
    temp = cal(x * 2, y, n, count+1);
    if (temp > -1) result.push_back(temp);
    temp = cal(x * 3, y, n, count+1);
    if (temp > -1) result.push_back(temp);
    
    if (result.size() == 0) return -1;
    else return *min_element(result.begin(), result.end());
}

int solution(int x, int y, int n) {
    int answer = 0;
    answer = cal(x, y, n, 0);

    return answer;
}

최종 풀이

메모이제이션으로 접근

#include <vector>

using namespace std;

int solution(int x, int y, int n) {
    int answer = 0;
    vector<int>result(y+1, y);
    result[x] = 0;
    for(int i=x; i<=y; i++)
    {
        int temp = i+n;
        if(temp<=y)
        {
            result[temp] = result[i]+1>result[temp]?result[temp]:result[i]+1;
        }
        
        temp = i*2;
        if(temp<=y)
        {
            result[temp] = result[i]+1>result[temp]?result[temp]:result[i]+1;
        }
        
        temp = i*3;
        if(temp<=y)
        {
            result[temp] = result[i]+1>result[temp]?result[temp]:result[i]+1;
        }
    }
    answer = result[y]==y? -1: result[y];
    return answer;
}

---

💡 느낀 점 (What I Felt)

항상 시간초과가 문제다. 시간 복잡도를 줄일 수 있게 알고리즘 공부를 많이 해야겠다.

---

출처 프로그래머스: 숫자 변환하기