글 읽기 - 예외 케이스

parksjin01 7년 전 0

이와 같이 소스를 짜서 제출했는데 0%에서 바로 틀렸다고 나오네요...

그런데 제 머리로는 어디가 잘못된건지 생각이 안나요

제가 고려하지 못한 케이스가 있을까요?

def make(num, cache):
    if num==1:
        return 0
    if cache[num]!=987654321:
        return cache[num]

    res=987654321
    if num%3==0:
        res=min(res, make(num/3, cache)+1)
    if num%2==0:
        res=min(res, make(num/2, cache)+1)
    if (num-1)%3==0:
        res=min(res, make((num-1)/3, cache)+2)
    if (num-1)%2==0:
        res=min(res, make((num-1)/2, cache)+2)

    cache[num]=res
    return res

n=input()
cache=[]
for i in xrange(n+1):
    cache.append(987654321)
print make(n, cache)
#print cache

dotorya 7년 전 0

num = 29일 때 정답이 안나올 것 같은데, 테스트는 안해봐서 잘 모르겠네요.

29 28 27 9 3 1이 올바른 순서이고

풀이에서는 2번 연속으로 1을 빼는 경우는 처리가 안돼서 29 28 14 7 6 3 1로 한번 더 걸릴것 같습니다.

parksjin01 7년 전 0

오 그렇네요

감사합니다

parksjin01 7년 전 0

오 그걸 고려할 수 있도록 고쳤더니 바로 통과됬습니다

정말 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

예외 케이스

parksjin01 7년 전 0

dotorya 7년 전 0

parksjin01 7년 전 0

parksjin01 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말