[프로그래머스] 숫자 변환하기 / 비둘기집의 원리

 

Level. 2

 

문제

자연수 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 <string>
#include <vector>

using namespace std;

int MIN = 1000001;
int countArr[1000001] = { 0, }; // 메모이제이션 

int convert(int count, int x, int y, int n){
    
    if( countArr[x] != 0 && countArr[x] <= count ) return countArr[x];
    
    countArr[x] = count;
   
    if(x == y) {
        return count;
    }
    
    int plus = MIN;
    int mul2 = MIN;
    int mul3 = MIN;
    
    if(x-n >= y){
        plus = convert(count+1,x-n, y, n);
    }
    
    if(x%2 == 0 && x/2 >= y){
        mul2 = convert(count+1,x/2, y, n);
    }
    
    if(x%3 == 0 && x/3 >= y){
        mul3 = convert(count+1,x/3, y, n);
    }
    
    return min(plus, min(mul2, mul3));
    
}

int solution(int x, int y, int n) {
    int answer = 0;
    
    answer = convert(0, y, x, n);
    
    if(answer >= MIN) return -1;
    
    return answer;
}

 

프로그래머스 내 질문목록을 참고하여 풀이하였다!

 

x에서 y 로 상향식 진행을 할 경우, 따져야 할 경우의 수가 많으므로

y에서 x로 하향식 진행을 해주었다. 

1. y에서 n을 빼는 경우

2. y를 2로 나누는 경우

3. y를 3으로 나누는 경우

 

이때 계산된 값에 대한 count가 중복되는 비둘기집의 원리 현상이 발생하는데

countArr배열을 사용하여 현재 값에 대한 count의 최솟값을 저장해 주어 해결하였다. 

 

 

 

---

다른 풀이

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int x, int y, int n) {
    queue<pair<int, int>> q;
    q.push(make_pair(y, 0));

    while (!q.empty())
    {
        int val = q.front().first;
        int count = q.front().second;
        q.pop();

        if (val == x)
            return count;

        if (val % 2 == 0)
        {
            q.push(make_pair(val / 2, count + 1));
        }

        if (val % 3 == 0)
        {
            q.push(make_pair(val / 3, count + 1));
        }

        if (val - n > 0)
        {
            q.push(make_pair(val - n, count + 1));
        }
    }

    return -1;
}

 

 

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/154538?language=cpp#

프로그래머스