[백준] 23082. 균형 삼진법

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

요약

• -1, 0, 1을 사용해서 삼진법으로 표현

접근법

• 공식풀이
• 어려웠던 문제였는데 난이도 투표는 그렇지 않다..
• 일단 음수는 모든 부호를 바꾸면 된다고 생각함
• 3진법으로 표현하는 방법은
  • 가장 근접한 ${ 3^n }$을 찾아서 빼고 나머지 숫자가 표현이 되는지 확인하거나
  • 한단계 큰 ${ 3^{n+1} }$에서 숫자를 빼서 가능한지 확인하거나로 생각함
• 그리고 되는 방향으로 탐색을 하는 방법으로 진행함
• 수의 범위로 인해서 3진법으로 표현하면 대략 20여개 깊이가 발생하므로 탐색공간이 ${ 2^20} $ 정도라고 생각했음
• 탐색을 하면서 앞 단계에서 어떤 숫자를 사용했는지도 체크하면서 내려감
• 탐색을 하면서 사용한 숫자를 모아두고 출력은 별도로 함(중간에 0 처리를 하려고)