글 읽기 - elif 일때 다르게나오는 이유??

janjju 2년 전 0

안녕하세요 풀다가 질문이 있어서 글을 남겨봅니다.

아래 두번째 if 부분에서 elif 로 변경할시에 틀리게 되는데

반례를 알수가 있을까요??

3으로 나눠지는데 그러지 않고 2로 나누는걸 먼저 실행한다는 소리인데(<- 이부분 잘 이해한건지도 알려주시면 감사합니다.)

계속 생각해봐도 반례가 잘 나오지않습니다ㅠㅠ

n = int(input())
d = [0]*1000001   
d[1]=0
d[2]=1      
d[3]=1      
d[4]=2      

for i in range(5, n+1):
    d[i] = d[i-1] + 1
    if i%3==0:
        d[i] = min(d[i], d[i//3]+1)
    if i%2==0:   # 이부분이 elif 라면
        d[i] = min(d[i], d[i//2]+1)

print(d[n])

lcr7324 2년 전 0

n = 642일 때 답이 다르게 나옵니다.

janjju 2년 전 0

n=642일떄

/2 먼저 하면 321

/3 먼저 하면 214 인데,

결국 두번째에서 반대로 각각 /3 /2 를 하면 107로 같아지는 개념과는 다른가요??

더 공부해야겠네요..ㅠㅠ

bamgoesn 2년 전 1

321은 정답이 9이고, 214는 정답이 10입니다. 이는 321을 1로 만드는 가장 짧은 과정이 321을 3으로 나누는 것이 아닌 1을 빼는 것으로 시작하기 때문입니다.

따라서 642는 실제로 2로 먼저 나누는 것이 정답인데, 3으로 나누는 경우만 확인하게 되어 오답이 나오게 됩니다.

10
321 320 160 80 40 20 10 9 3 1

9
320 160 80 40 20 10 9 3 1

10
107 106 53 52 26 13 12 4 2 1

janjju 2년 전 0

와 다들 답변 감사합니다..

kwonjoosung 1년 전 0

감사합니다! 저도 이 부분에서 한참 헤맸네요...

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

문제

문제

출처

ICPC

elif 일때 다르게나오는 이유??

janjju 2년 전 0

lcr7324 2년 전 0

janjju 2년 전 0

bamgoesn 2년 전 1

janjju 2년 전 0

kwonjoosung 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말