글 읽기 - 반례를 찾아주세요

rudtn0403 2년 전 0

균형 3진법을 어떻게 계산해야 되는지 몰라서 어떻게든 예시가 가능하게 만들었습니다만
반례가 있는 것 같습니다. 반례와 균형 3진법 변환 방법을 알려주시기 바랍니다.

import sys
n = int(sys.stdin.readline())
ans = ""
min=True
a = 0
num=0
if n<0:
    min=False
    n = abs(n)
while a<n:
    a += 3**num
    num+=1

if min:
    for i in range(num):
        if n%3==2:
            ans = "T"+ans
        else:
            ans = str(n%3) + ans
        n = n//3
else:
    for i in range(num):
        if n%3==1:
            ans = "T"+ans
        elif n%3==2:
            ans = "1"+ans
        else:
            ans = str(n%3) + ans
        n = n//3
print(ans)

djs100201 2년 전 0

반례 8
출력 0TT
정답 10T

균형 3진법 만드는 방법

어떤 string s가 균형삼진법 x의 표현이라고 하면, s+'0'을 하게 되면 3x, s+'1' 을하게 되면 3x+1 s+'T' 를 하게 되면 3x-1입니다. 모든 정수는 3n,3n-1,3n+1 3가지 중에 하나로 표현되므로 모든 정수를 유일하게 표현할 수 있습니다. 음수면 다 뒤집어 주면 됩니다.

rudtn0403 2년 전 0

소스를 잘못 올렸네요.
위의 설명은 알고 있습니다만 3진법처럼 n//3으로 나누기만 하면 균형 3진법이 되질 않습니다.
41의 예를 들자면
3진법의 경우는

1112로 표현 되지만

균형 3진법의 경우

1TTTT로 표현됩니다.

3진법 변환법에서 어떻게 변형해야 균형 3진법으로 변환시킬 수 있을지 감이 안옵니다.

import sys
n = int(sys.stdin.readline())
ans = ""
min=True
a = 0
num=0
if n<0:
    min=False
    n = abs(n)
while a<n:
    a += 3**num
    num+=1

if min:
    for i in range(num):
        if n%3==2:
            ans = "T"+ans
        else:
            ans = str(n%3) + ans
        n = (n+1)//3
else:
    for i in range(num):
        if n%3==1:
            ans = "T"+ans
        elif n%3==2:
            ans = "1"+ans
        else:
            ans = str(n%3) + ans
        n = (n+1)//3
    
print(ans)

djs100201 2년 전 0

41은 3으로 나눈 나머지가 2입니다. 따라서 맨 뒤에 T를 push 합니다.
그럼 42가 되겠죠

3으로 나눕니다. 14가 됩니다.
다시 나머지가 2이니까 T를 push 합니다.
그럼 15가 되고 3으로 나누면 5가 됩니다.
다시 T를 넣고 3으로 나누면 2가 됩니다.T를 넣고 마지막엔 1이 되니까 1을 넣어주시면 1TTTT가 됩니다.
그 다음 뒤집으면 되겠죠. 비슷한 방식으로 하신거 같은데 음수일때나 0일때 잘 처리해주면 됩니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 찾아주세요

rudtn0403 2년 전 0

djs100201 2년 전 0

rudtn0403 2년 전 0

djs100201 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말