[BOJ/백준] 2089 -2진수

● [문제번호 2089] -2진수

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

2089번: -2진수

 

● 알아야 할 것

: -2진법에 대한 이해

 

● 풀이 과정

: 양수로 된 진수는 알고있었지만 음수로 된 진수는 처음 접하여 이해하기 어려웠다.

그래서 구글링 결과 방법은 2진수, 8진수 등과 다를 바 없었다.

하지만 구하는 과정에서 부호와 함께 고려해야하는 것이 있다.

 

: 10진수 → -2진수 로 바꾸는 과정에서

3가지 경우 중 1가지를 선택하며 0이 될 때 까지 반복한다.

 

1. 2로 나눠지는 경우

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

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

 

● 주의 할 것

: 재귀 호출 → 재귀 종료 → 출력이어야

-2진법의 수가 거꾸로 출력되지 않는다.

 

● 참고 할 것

: -2진수를 이해하기 위한 링크 (일반화하여 N진수에 대해서 설명되어 있다.)

https://softworking.tistory.com/18

 

: 문제 이해와 풀이를 위한 링크

https://m.blog.naver.com/legendmic2/221843913117

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

int N;

// -2진법을 출력하기 위한 함수
// 재귀를 사용할 때
// 재귀 호출 → 재귀 종료 → 출력
// 이 순서로해야 -2진법의 수가 거꾸로 출력되지 않는다
void minus_two(int n)
{
    // 재귀의 base case
    if(n == 0)
        return;
    
    // 경우 1. 2로 나눠지는 경우
    if(n % 2 == 0)
    {
        minus_two(-(n / 2));
        cout << 0;
    }
    else
    {
        // 경우 2-1. 2로 나눠지지 않는 경우 + 양수 인 경우
        if(n > 0)
            minus_two(-(n / 2));
        
        // 경우 2-2. 2로 나눠지지 않는 경우 + 음수 인 경우
        else
            minus_two((-n + 1) / 2);
        
        cout << 1;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    // 입력
    cin >> N;
    
    // 초기 입력값이 0인 경우 처리
    if(N == 0)
        cout << 0;
    else
        minus_two(N);
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [301 - 수학 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	9613	GCD 합	https://pirateturtle.tistory.com/189
2	17087	숨바꼭질 6	https://pirateturtle.tistory.com/190
3	1373	2진수 8진수	https://pirateturtle.tistory.com/191
4	1212	8진수 2진수	https://pirateturtle.tistory.com/192
5	2089	-2진수	https://pirateturtle.tistory.com/193
6	17103	골드바흐 파티션	https://pirateturtle.tistory.com/194