[BOJ]2089번: -2진수(java, c++)

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

2089번: -2진수

 

방법 1: 나머지 정리 이용

import java.io.*;
import java.util.Stack;
 
public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringBuilder sb = new StringBuilder();
            int Decimal = Integer.parseInt(br.readLine());
 
            while (true) {
                int rest = Decimal % -2;
                rest = (rest < 0) ? rest * -1 : rest;
                sb.append(rest);
                
                Decimal = (Decimal - rest) / -2;
 
                if (Decimal == 0) {
                    break;
                }
            }
            
            System.out.println(sb.reverse());
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

 

 

방법 2: -2진법 구현

#include <iostream>
#include <stack>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
 
    // 0일경우 예외처리
    if (n == 0)
    {
        cout << 0;
        return 0;
    }
 
    stack<int> s_mbin;
    while (n != 0)
    {
        int quot = n / -2;
 
        // 나머지가 없을 때
        if (n % -2 == 0)
        {
            s_mbin.push(0);
            n = quot;
        }
        // 나머지가 있을 때
        else
        {
            // ex) -13 / -2 = 6 ... 1 인데,
            //     -2 * (6 + 1) + 1 = -13 처럼 원상복귀 할때 몫에 1이 더 필요한 경우
            if (n < 0)
            {
                n = quot + 1;
            }
            // ex) 7 / -2 = -3 ... 1 인데,
            //    -2 * -3 + 1 = 7의 경우
            else
            {
                n = quot;
            }
            s_mbin.push(1);
        }
    }
 
    while (!s_mbin.empty())
    {
        cout << s_mbin.top();
        s_mbin.pop();
    }
 
    return 0;
}

 

아무래도 방법 2가 더 간단하다 ㅎㅎ

 

 

TIP1 - 방법2

숫자 N을 -2로 나눴을 때, 나머지가 발생하는 케이스가 2가지로 나뉜다.

1. 숫자 N이 음수. 그리고 몫 * -2 + 1이 숫자 N과 -2 차이날때. 

2. 숫자 N이 양수. 그리고 몫 * -2 + 1이 그대로 숫자 N일때.

 

결국 간단하게 N의 음수/양수 여부로 분개를 칠 수 있다.

1번 케이스는 나뉘어지는 수가 음수라서 발생하는 케이스.

 

 

 

TIP2

 

방법 1은 다음과 같은 나머지 정리를 이용한다

숫자 N 을 X로 나눠서 나머지가 발생할 때마다 답안에 집어넣기