Boj 34620 군꺾문자열 c++

https://www.acmicpc.net/problem/34620

 

분모가 2의 제곱수인 기약분수를 2개의 연산으로 표현할 수 있는 가장 짧은 문자열을 구하는 문제.

진법 변환의 원리에 대한 사전지식이 있어야 한다.

 

우선 분모가 2의 제곱수가 아닌 숫자는 배제시켜야 하기 때문에 and 연산자를 통해 걸러내었다.

어떤 숫자가 2의 제곱수일 때 그 숫자에서 1을 뺀 값과 곱 연산을 했을 때는 0이 나온다.

ex )  8 --> 1000, 7 ---> 0111

8 & 7 ----> 0

 

 

그 후에는 가장 짧은 문자열을 찾는 과정이다.

숫자를 쌓는 방식은 다음과 같다.

3 / 8은  1 / 4 + 1 / 8 이다.

이는 다시 

(1 / 2 + 1 / 4) / 2

(1 + 1 / 2) / 2 / 2

로 표현이 가능하며 이때의 최소 길이 문자열은 

G K G K K 이다.

 

원리가 조금 어렵게 느껴진다.

가장 초반에 더한 1이 그 숫자의 가장 작은 2의 제곱수 분모로 들어가는 것이다.

 

하지만 이렇게 어렵게 생각할 문제는 아니였다.

 

이 문제에서 주어진 연산은 단 2가지.

1. 숫자에 1을 더한다

2. 숫자를 2로 나눈다.

 

이다.

 

주어진 기약 분수 또한 그러한 과정을 거쳐왔을 것임을 유추할 수 있다.

또한 주어진 숫자는 반드시 1보다 작기 때문에 1을 더한 연산 후에는 반드시 2로 나눈 연산이 나타날 것 또한 예상할 수 있다.

 

그렇다면 숫자에 대한 연산을 거꾸로 따라가면 되는 것이다.

 

3 / 8

=  3 / 4  *  1 / 2

= 3 / 2  * 1 / 2  * 1 / 2

= (1 + 1 / 2)  * 1 / 2 * 1 / 2

= ((0 + 1) * 1 / 2 + 1)  * 1 / 2 * 1 / 2

 

와 같은 형태를 따르는 것이다.

 

원래의 연산은 +1과 나누기 2였다면 이번에는 해당 숫자에서 -1과 곱하기 2 만으로 0에 도달하는 경로를 찾으면 되는 것이다.

두 연산을 하는 시점은 해당 숫자가 1보다 작은 경우에는 * 2,  1보다 큰 경우에는 -1을 해주면 되는 것이다.

 

연산순서를 구하기 위해서는 역산한 순서를 뒤집으면 된다.

 

이 문제의 그리디 전략은 사전순으로 가장 짧은(더하기 연산을 먼저 하는) 연산은 

해당 숫자에서 0으로 도달하는 경로와 동일하다는 것이였다.

 

앞으로도 처음에서 끝으로 도달하는 것이 험난해보인다면 역산을 해보는 시도를 해보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

    int a, b;
    vector<char> ans;
    cin >> a >> b;

    if(b & (b-1)) {
        cout << "-1";
        return 0;
    }

    while(a) {
        if(a >= b) {
            a -= b;
            ans.push_back('G');
        } else {
            b >>= 1;
            ans.push_back('K');
        }
    }
    reverse(ans.begin(), ans.end());
    for(char a : ans) {
        cout << a;
    }
}
/*
3 / 8
1/ 4 + 1 / 8
(1 / 2 + 1 / 4) / 2
(1 + 1 / 2) / 2 / 2
1 / 2 + 1
1 / 8
K K K G K G
3 */