[C++]백준 - 23082번 문제

23082번: 균형 삼진법 (acmicpc.net)

23082번: 균형 삼진법

 

23082번 : 균형 삼진법

---

균형 삼진법은 밑이 3이고, 자릿수가 0, 1, −1로 이루어진 기수법이다.

이를 이용해 별도의 부호를 사용하지 않고서도 모든 정수를 유일한 방법으로 나타낼 수 있다.

십진수를 입력 받아 균형 삼진법으로 출력하는 프로그램을 작성하시오.

 

입력

---

십진법으로 나타낸 정수 N이 주어진다.

 

• -10 ^ 9 ≤ N ≤ 10 ^ 9

 

 

출력

---

문제의 정답을 출력한다. 자릿수가 −1이라면 대신 'T'를 출력한다.

 

 

 

 

---

 

생각해 볼 점

---

메모장으로 고민해보면서..

 

조건을 넣어 음수 양수 변환하는 시뮬레이션이나

그냥 수학처럼 3진수 올림 풀이를 하는 경우를 생각해봤는데

 

결국 올림 연산 풀이가 가장 좋은 것 같습니다.

 

제가 푼 방법이 정석은 아닐수도 있습니다.

 

1. 일반적인 3진수로 변환한다.

2. 변환된 3진수를 오른쪽부터 읽는다.

 

2-1. 읽은 숫자에 + 1을 수행한다.

2-2. 숫자가 3 이상일 경우 3을 빼고 올림한다.

2-3. 숫자가 양수였을 경우, 0 => T / 1 => 0 / 2 => 1 로 변환한다.

2-3. 숫자가 음수였을 경우, 0 => 1 / 1 => 0 / 2 => T 로 변환한다.

 

3. 마지막으로 올림이 있으면 앞자리에 1 혹은 T를 추가한다.

 

숫자가 양수였을 경우, 1

숫자가 음수였을 경우, T

 

예시로 14를 들겠습니다.

 

예시) 14

 

1. 3진수화

14 -> 112

 

2. 모든 자리수 + 1

112 -> 223

 

3. 올림수 연산 (3일 경우 앞자리에 1을 더하고 -3) 및 부호에 따라 값 변경

223 -> 230 -> 300 -> 1000 -> 1TTT 

 

4. 맨 앞자리 올림 수가 있을 경우 부호에 따라 1 혹은 T를 붙임

 

1TTT

 

코드

---

#include <iostream>
#include <cmath>
#include <string>
using namespace std;


int main()
{
	int N;
	cin >> N;
	string ans = "";
	int is_minus = N < 0 ? 1 : 0;
	if (is_minus) N *= -1;

    //음수와 양수에 따라 넣을 문자 변경
	char cache[2][3] = { { 'T',  '0', '1' }, {'1', '0', 'T'} };

    //original 3진수
	while (N)
	{
		ans.insert(0, 1,N % 3 + 48);
		N /= 3;
	}

    //올림
	int upper = 0;
    
    // 3진수 -> 균형 삼진수 알고리즘
    // 1. original + 1, 예시 : 122 -> 233
    // 2. 맨 끝자리부터 3 이상일 경우 올림 후 -3, 예시 : 233-> 010
    // 3. cache의 index에 대입하여 문자 변경, 예시 : 010 -> T0T
    // 4. 마지막 올림이 있을 경우, 양수면 '1', 음수면 'T'추가. 예시 : T0T -> 1T0T 
	for (int i = ans.size() - 1; 0 <= i; i--)
	{
		int cur = ans[i] - 47 + upper;
		if (2 < cur)
		{
			upper = true;
			cur -= 3;
		}
		else upper = false;

		ans[i] = cache[is_minus][cur];
	}
	if (upper) ans.insert(0, 1, cache[!is_minus][0]);

    if(ans.empty()) ans = "0";
	cout << ans;
	
	return 0;
}

 

그 외

---