[백준] 2089번: -2진수

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

문제

알고리즘 접근 방법

음수 진수는 구하는 과정에서 부호와 함께
고려해야하는 것이 있다.
: 10진수 → -2진수 로 바꾸는 과정에서
3가지 경우 중 1가지를 선택하며 0이 될 때 까지 반복한다.

1. 2로 나눠지는 경우

n = -(n / 2);

2-1. 2로 나눠지지 않는 경우 + 양수 인 경우

n = -(n / 2);

2-2. 2로 나눠지지 않는 경우 + 음수 인 경우

n = (-n + 1) / 2; 

-13을 예를 들어보자

result = '';

1) n = -13

2-2. 2로 나눠지지 않는 경우 + 음수 인 경우

-13/2 = 7 ... 1
n = (-n+1)/2  = 14/2 = 7
검토) 7*(-2)+1 = -13  => n 과 같다.

result = 1

2) n = 7

2-1. 2로 나눠지지 않는 경우 + 양수 인 경우

7/2 = 3 ... 1
n = -(n / 2); = -(7/2) = -3
검토) (-3)*(-2) + 1 = 7  => n 과 같다.

result = 11

3) n = -3

2-2. 2로 나눠지지 않는 경우 + 음수 인 경우

-3/2 = 2 ... 1
n = (-n+1)/2  = 4/2 = 2
검토) 2*(-2)+1 = -3 => n 과 같다.

result = 111

4) n = 2

1. 2로 나눠지는 경우

2/2 = 1 ... 0
n = -(n / 2) = -(2/2) = -1
검토) 1*2+0 = 2 => n 과 같다.

result = 0111

5) n = -1

2-2. 2로 나눠지지 않는 경우 + 음수 인 경우

-1/2 = 1 ... 1
n = (-n+1)/2  = 1
검토) 1*(-2)+1 = -1 => n 과 같다.

result = 10111

6) n = 1

2-1. 2로 나눠지지 않는 경우 + 양수 인 경우

1/2 = 0 ... 1
n = -(n / 2); = -(1/2) = 0
검토) 0*(-2) + 1 = 1  => n 과 같다.

result = 110111

6) n = 0

끗

풀이

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int N;

void trans(int n){

    if (n == 0)
        return;

    // 경우 1. 2로 나눠지는 경우
    if (n % 2 == 0){
        trans(-(n/2));
        cout << 0;
    }
    else{
        // 경우 2-1. 2로 나눠지지 않는 경우 + 양수 인 경우 
        if(n > 0) 
            trans(-(n / 2)); 
        // 경우 2-2. 2로 나눠지지 않는 경우 + 음수 인 경우 
        else 
            trans((-n + 1) / 2);
        cout << 1;
    }
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    if (N == 0)
        cout << 0;
    else   
        trans(N);
    
    cout << '\n';

    return 0;
}

정리

잘 모르겠어서 따라가면서 푸는데.. 잘 모르겠다.,

💡 참고 포스팅

해적거북님 블로그
컴공맨님 블로그
minyeok2ee님 블로그