글 읽기 - 틀렸다고 나오는데 왜 그럴까요?(파이썬)

gold9962 3년 전 0

수 순차적으로 1~15까지 대입해도 답으로 나오는데 도대체 어떤 곳에서 틀렸는지 모르겠어요...

X = int(input())

dp = [0, 0, 1, 1]

for i in range(4, X+1):
    if (i%3 == 0):
        cnt = 1+ dp[i//3]
    elif (i%2 == 0):
        cnt = 1 + min(dp[i-1], dp[i//2])
    else:
        cnt = 1 + dp[i-1]
    dp.append(cnt)

print(dp[X])

luniro 3년 전 1

입력이 28일 때 답이 4로 나오나요?

gold9962 3년 전 0

네...!!

djm03178 3년 전 1

3으로 나누어 떨어진다고 바로 나누는 게 이득이 아닐 수도 있습니다.

luniro 3년 전 2

3으로 나누는게 이득이 아닌 반례들입니다

입력 정답 출력
321   9  10
609  10  11
642  10  11
643  11  12
645  11  12
963  10  11

gold9962 3년 전 0

아!! 다들 감사합니다!ㅎㅎ

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

문제

문제

출처

ICPC

틀렸다고 나오는데 왜 그럴까요?(파이썬)

gold9962 3년 전 0

luniro 3년 전 1

gold9962 3년 전 0

djm03178 3년 전 1

luniro 3년 전 2

gold9962 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말