2089번 -2진수 - ☆

#문제링크 : https://www.acmicpc.net/problem/2089

<전략>

1. -2로 나누고 나머지 연산을 하면 2로 나누고 나머지 연산을 했을때와 다르다. 2로 나누었을 때는 나머지가 항상 +1, 0 이지만 -2로 나누었을 때는 나머지가 항상 -1, 0이 된다. 이 나머지를 양수로 바꾸어 주어야 원하는 다항식이 나온다.

2. -2로 나누었을때, 나머지가 0인 경우와 나머지가 0이 아닌경우로 나눈다. 나머지가 0인 경우, 그 다음 n값은 n/-2 로 하면 되고, 나머지가 0이 아닌 경우에는 다시 한번 더 경우를 나누어야 한다. 나머지가 0이 아니면서, n이 양수면, 나머지는 +1이 되므로 기존 진법연산과 같이 하면된다. 하지만 나머지가 0이 아니면서, n이 음수인 경우는 나머지가 -1이기 때문에 몫을 하나 증가시켜 주고 나머지를 +1로 만들어줘야 한다. 즉, 예를 들어 -5를 -2로 나눈다 하면, -5 = -2*2 - 1 이되므로 몫인 2를 3으로 하나 증가시켜서 -5 = -2*3 + 1로 바꾸어준다는 소리다. 이렇게 경우를 나누어 반복문에 작성하면 해결할 수 있다.

3. 처음에 생각했을때는, 경우를 나눌때, n이 음수라면 무조건 몫을 하나 증가시키고, 양수면 그대로 하는 방법으로 했는데, 논리 자체에 오류가 있었다. 먼저, n을 나누었을 때 나머지가 0인지 아닌지부터 따져줘야 한다.

Code