[BOJ/백준] 23082 균형 삼진법 C++

내 첫 포스팅은 23082번 균형 삼진법 문제이다.

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

23082번: 균형 삼진법

이 문제를 선택한 이유는... 뭐... 구글에 검색해서 잘 나오지도 않고...

인하대 학우들이나 오픈 콘테스트 나가는 사람들이 언젠가 IUPC를 준비할 때 도움이 되지 않을까 하는 마음에 작성해 본다!

균형 삼진법 문제의 첫 접근 자체가 어지럽다. 이게 뭔 말인가... 싶기도 하고, 구현 자체를 쌩으로 하나하나 해야 하는 것인가에 대한 의문도 든다.

이 문제를 푸는 방법은 여러 가지가 있겠지만, 크게 두 가지로 나뉘는 것 같은데... 

 

첫 번째는 직관적으로 그냥 생짜로 구현 때리는 거다. 이것에 관한 설명은 2021 IUPC 솔루션을 참조해 보자.$( $이건 뭐... 쉽지 않다... $)$

 

두 번째는 3진법의 표현을 구한 뒤 그에 맞춰 코드를 짜주는 것이다. 표현을 자세히 보기 위해 아래의 필기를 보자.

 

필기만 보면 이게 무슨 소리인가... 싶겠지만... 굉장한 통찰력이 담겨있다. $($필자는 바로 못 떠올림 ㅎㅡㅎ;;$)$

일단 주어진 수 N에 대하여 3으로 나누면서 나머지를 옆에 표시한다. 이러한 방식은 십진법에서 이진법으로 변환하는 과정과 크게 다르지 않아서 자주 접해본 과정일 것이다. 이 과정 중 나머지는 1, 0, 2가 나올 것이고, 2가 나올 경우에는, 2가 나온 수를 -1로 바꿔주고, carry를 1 올려주면 된다. 그렇다면, 만약 주어진 수 N이 17이라면 어떻게 될까? 

 

이런 식으로 될 것이다. 예외적으로 3이 발생하면 그냥 2만 -1로 바꿔주고, carry로 보낸 다음, 1을 더해주는 식으로 해결하면 된다.

아 그리고, 음수로 N이 주어지면 -1을 곱해주고 답을 구한 뒤 1은 T로, T는 1로 바꿔주면 된다.

 

정답 코드는 아래를 확인하자!

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

int N;
int k[5001]={0, };
stack<char> s;

int main(){
   cin.tie(nullptr)->ios_base::sync_with_stdio(false);
   cin>>N;
   if(N==0){
      cout<<0<<'\n';
   }
   else{
      int i=0;
      bool flag=true;
      if(N<0){
         N*=(-1);
         flag=false;
      }
      while(N){
         k[i]=N%3;
         N/=3;
         i++;
      }
      for(int j=0; j<i; j++){
         if(k[j]==2){
            k[j+1]++;
            s.push('T');
            i++;
         }
         else if(k[j]==1){
            s.push('1');
         }
         else if(k[j]==0){
            s.push('0');
         }
         else{
            k[j+1]++;
            k[j]-=3;
            j--;
         }
      }
      while(s.top()=='0'){
         s.pop();
      }
      if(flag){
         while(!s.empty()){
            cout<<s.top();
            s.pop();
         }
      }
      else{
         while(!s.empty()){
            char ch = s.top();
            s.pop();
            if(ch=='1'){
               cout<<'T';
            }
            else if(ch=='T'){
               cout<<'1';
            }
            else{
               cout<<ch;
            }
         }
      }
   }
   return 0;
}

솔직히 말해서, 두 번째 풀이의 성질을 알고 있는 거 아니면 첫 번째 풀이로 풀어야 한다는 것인데... 대회장에서 시간 쫓기는 데에 풀기엔 쉽지 않을 것 같은 느낌이 드는 문제였다...

 

 

나의 첫 포스팅 끝~!