[코드트리/C++] 곱빼기 (Math)

문제

https://www.codetree.ai/problems/mul-minus/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

구상

문제 자체는 거창해보이지만, 사실 생각할 거리가 조금 있는 비교적 쉬운 문제였다. 우선, while문을 통해 목표값보다 크거나 같은 가장 작은 2의 거듭제곱을 찾는다. 이때 값과 함께 shift 수도 구해야 한다. 그리고,  해당 값과 구해야하는 값을 빼서 남은 값을 계산한다. 남은 값을 2의 거듭젭곱으로 분해해야하는데, 해당 과정이 조금 어렵다. 

 

우선,  8이 2^3 이라는 점을 알고 있으니, 이를 가지고 2의 거듭제곱으로 분해하는 풀이를 생각해보자. 8을 2로 3번 나누면 4 -> 2 -> 1이 된다. '1'이라는 값이 되었을 때 3이라는 거듭제곱을 도출할 수 있다. 7의 경우는 어떨까? 우선 2로 나누면 몫이 3에 나머지가 1이다. 그리고, 몫인 3을 또 2로 나누면 몫이 1에 나머지가 1이다. 그리고 이때 몫인 1을 2로 나누면 몫이 0에 나머지가 1이다. 이렇게 몫이 0일때까지 2로 나누되, 나머지가 1인 경우에 0부터 1씩 증가하며 값을 출력하면 0, 1, 2가 도출된다. 8의 경우에도 2로 나눌때마다 도출하는 값을 1씩 증가시키되, 0 -> 1 -> 2 -> 3 에서 나머지가 1이 나오는 가장 마지막 상황인 3만 도출되게 된다. 이러한 풀이로 코드를 짜면 아래와 같이 나온다.  주의할 점은 해당 값들은 오름차순으로 구해지기에 출력할때는 거꾸로 출력해야 한다. 

 

풀이 + 코드

#include <iostream>
#include <vector>
using namespace std;
// 곱빼기 

int main() {
    int target;
    cin >> target;
    
    int current_value = 1;
    int shift_count = 0;
    vector<int> shift_positions;
    
    // 목표 값보다 크거나 같은 가장 작은 2의 거듭제곱 찾기
    while (current_value < target) {
        shift_count++;
        current_value *= 2;
    }
    shift_positions.push_back(shift_count);
    // 현재 값에서 목표 값을 빼서 남은 값 계산
    current_value -= target;
    shift_count = 0;
    
    // 남은 값을 2의 거듭제곱으로 분해
    while (current_value) {
        // 현재 값이 홀수인 경우, 해당 시프트 횟수를 저장
        if (current_value % 2) {
            shift_positions.push_back(shift_count);
        }
        shift_count++;
        current_value /= 2;
    }

    // 시프트 위치를 출력
    if (shift_positions.size() == 1) {
        cout << shift_positions[0] << endl;
    } else {
        cout << shift_positions[0];
        for (int j = shift_positions.size() - 1; j > 0; j--) {
            cout << " " << shift_positions[j];
        }
        cout << endl;
    }
    
    return 0;
}