[백준] 17497 계산기

 

생각을 결국 떠올리지 못한 문제다!!

한번 2진수로 생각을 해보자

N -> 0까지 갈 예정이다

그럼 내가 0번째 비트가 1이라면 사라지게 할 방법이 없다

그래서 뒤로 한칸 밀어버려야한다(곱하기)

만약 1번째 비트가 1이라면 결국 2라는 값이 포함된다는 말이고

2를 빼면 된다는 말이다(빼기)

만약 0,1비트가 다 0이면 계속 앞으로 땡겨오자(나누기)

 

그럼 결론적으로 10^13 => 2^45승 정도의 비트를 이런식으로 다 처리하면 된다

N부터 거꾸로 보기때문에 반대로 연산자를 담아주자

 

0번째 비트가 1인경우,0인경우를 다 생각해보면 어떻게해도 99번을 넘지 않는다

신기하고 쉬워보이지만 나에게는 처음에 어려운 문제였따..!!

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
ll n;
vector<char> vt;
int main(){
    scanf(" %lld",&n);
    while(n){
        if(n&1) {
            vt.push_back('/'); n*=2;
        }
        else if(n&2){
            vt.push_back('+'); n-=2;
        }
        else {
            vt.push_back('*'); n/=2;
        }
    }
    if(vt.size() >99) puts("-1");
    else {
        printf("%d\n",(int)vt.size());
        for(int i=(int)vt.size()-1; i>=0;i--) printf("[%c] ",vt[i]);
    } 
}