[java 백준] 실버 4/ 2089번 -2진수

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

2089번: -2진수

import java.io.IOException;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
 
        int num = sc.nextInt();
        String result = "";
        if (num == 0) {
            System.out.println(num);
            return;
        }
        while (num != 0) {
            if (num % -2 == -1) {
                result = (num % -2) + 2 + result;
                num = (num / -2) + 1;
            } else {
                result = (num % -2) + result;
                num = num / -2;
            }
        }
        System.out.println(result);
    }
 
}

 

 

처음엔 dp로 풀어보려했다. 마지막 숫자가 10,11,00,01로 반복되었기 때문에..

하지만 이렇게하면 생각해줘야할 가짓수가 너무 많아져서 비효율적이라는 생각을 했고 -2로 나눠보는게 어떨까 라는 생각을 했다.

근데 딱 -2로 나눠보자는 생각밖에 못했다..ㅋㅋㅋ

 

그래서 다른사람들의 코드를 참고했다.

 

예를 들어 -13이 있을 때

 

-13 =(-2)*7+1

7=(-2)*(-3)+1

-3=(-2)*2=+1

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

-1=(-2)*1+1

1=(-2)*0+1

0--> while문 빠져나옴

여기서 나머지만 보면 110111이 된다!

 

처음 쓴 코드 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int num = Integer.parseInt(br.readLine());
        String[] arr = { "00", "01", "10", "11" };
        String[] result = null;
        if (num == 0) {
            System.out.println(num);
 
        }
        int nums = 0;
        if (num != 0) {
            if (num > 0) {
                nums = num;
            } else if (num < 0) {
                nums = -num;
            }
            result = new String[nums + 1];
            result[1] = "1";
            for (int i = 2; i <= nums; i++) {
 
                if (i > 5) {
                    result[i] = result[i / 5 + 1] + arr[i % 4];
 
                } else {
                    result[i] = result[1] + arr[i % 4];
                }
            }
 
            String ans = "";
            if (num < 0) {
                num = -num;
 
                if (num == 1) {
                    ans = "11";
                } else if (num == 2) {
                    ans = "10";
                }
                if (num > 2 && num % 2 == 0) {
 
                    System.out.println(result[num / 2] + "0");
 
                } else if (num > 2 && num % 2 == 1) {
 
                    System.out.println(result[(num + 1) / 2] + "1");
                }
            } else if (num > 0) {
                System.out.println(result[num]);
            }
 
        }
 
    }
 
}

거의 무지성으로 풀었다 ㅋㅋㅋㅋㅋ 앞서 말했던 끝자리의 반복을 이용했는데, 이렇게 하면 엄청 큰수가 나왔을 때 메모리초과가 나오게된다. 물론 내가 틀린 이유도 메모리 초과였다 ㅋㅋ