글 읽기 - 혹시 어떤 부분에서 틀린 걸까요?

csw9595 3년 전 0

각 비교조건을 잘 잡아놓은 거 같은데 (cmp로) 어디서 틀린 건지 잘 모르겠습니다.

cur, target = map(int, input().split())

time = 0
while cur != target:
    if cur - 1 == target or cur + 1 == target or cur * 2 == target:
        time += 1
        break
        
    if target - cur < 0:
        cur -= 1
        time += 1
    else:
        if (target - cur) > cur * 2:
            cur *= 2
            time += 1
    
        else:
            cmp = list(map(abs, [target - (cur + 1) * 2, target - (cur - 1 ) * 2, target - cur * 2]))
            idx = cmp.index(min(cmp))
            if idx == 0:
                cur = (cur + 1) * 2
                time += 2
            elif idx == 1:
                cur = (cur - 1) * 2
                time += 2
            else:
                cur = cur * 2
                time += 1


print(time)

dldyddlwl 3년 전 0

반례]

1 5

예상값] 1, 2 -> 4 -> 5 , 3번

글쓴이님 코드] 4번

 cmp = list(map(abs, [target - (cur + 1) * 2, target - (cur - 1 ) * 2, target - cur * 2]))
            idx = cmp.index(min(cmp))
        
# 우선 min이 가장 처음 만난 최솟값을 리턴해야한다는 것을 아셔야 합니다, index도 마찬가지입니다.

# 위 예시로 설명하겠습니다
# 우선 1 -> 2 는 자명합니다. 문제는 2 -> 4로 가지 못한다는 것입니다.

# target - cur = 4 > 2* cur = 4 조건에 맞지 않아 아래의 else 구문으로 들어가게 됩니다.
# 그런데 target - (cur+1) *2 = 5 - 6 = -1 입니다.
# 그리고 target - (cur-1) *2 = 5 - 2 = 3 입니다
# 마지막으로 target-cur*2 = 5-4 = 1입니다.

# 가장 가까운 것은 마지막 target-cur*2 입니다. 하지만 min은 가장 처음 만난 최솟값인 -1 을 선택하게 되고,
# index 또한 가장 처음 만난 최솟값 1인 0번을 리턴하므로,
# 아래의 idx == 0 구문으로 들어가버리게 됩니다!
# 그렇게 되면 1 -> 2 -> 3 -> 6 -> 5 가 되어버려서 오답이 됩니다.

        else:
            cmp = list(map(abs, [target - (cur + 1) * 2, target - (cur - 1 ) * 2, target - cur * 2]))
            idx = cmp.index(min(cmp))
            if idx == 0:
                cur = (cur + 1) * 2
                time += 2
            elif idx == 1:
                cur = (cur - 1) * 2
                time += 2
            else:
                cur = cur * 2
                time += 1

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

문제

문제

출처

ICPC

혹시 어떤 부분에서 틀린 걸까요?

csw9595 3년 전 0

dldyddlwl 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말