글 읽기 - [Python] 반례를 못찾겠습니다.

yordlejason 6년 전 0

질문게시판에서 왠만한 반례들은 다 찾아봤는데, 정상적으로 작동했습니다.

문제에서 제시한 제일 큰 수를 넣었을 때에도 정상적으로 작동을 했구요.

다만, 문제 제출을 했을때 틀렸다고 나오는것을 보니 제가 캐치하지 못한 반례가 있는것같은데,

그게 당최 어느부분인지 모르겠습니다.

고수분들 반례좀 부탁드립니다.

감사합니다 :-)

def make_one_bottom_to_top(x):
    d = {1: 0}
    for n in range(2, x+1):
        d[n] = d[n-1] + 1                     # n - 1 case
        if n % 2 == 0 and d[n-1] > d[n//2]:   # n % 2 case
            d[n] = d[n//2] + 1
        elif n % 3 == 0 and d[n-1] > d[n//3]: # n % 3 case
            d[n] = d[n//3] + 1
    return d[x]
print(make_one_bottom_to_top(int(input())))

jwvg0425 6년 전 1

n % 3 == 0 and d[n-1] > d[n//3]

요부분이 좀 이상해보이긴 하네요. d[n-1] >d[n//2]인데 d[n//2] > d[n//3]인 경우는 어떻게 되나요? 이때 2번째 케이스로 들어갈텐데 실제론 3번째 케이스가 답이 되어야하는게 아닌지..

yordlejason 6년 전 0

@jwvg0425

말씀해주신것 처럼 공배수가 되는 경우를 빼먹었네요!...

감사합니다 :-)

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

문제

문제

출처

ICPC

[Python] 반례를 못찾겠습니다.

yordlejason 6년 전 0

jwvg0425 6년 전 1

yordlejason 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말