[백준,Python]16953번 A->B(Greedy)

[백준,Python]16953번 A->B(Greedy)

 

www.acmicpc.net/problem/16953

16953번: A → B

 

이번 문제는 빠른 시간안에 문제 해결을 하였지만, 시간 초과 문제로 여러가지 고민을 하게 만들었던 문제이다.

 

문제 해결 알고리즘은 B를 처음에 10으로 나눈 나머지가 1인 것 체크하고 다음으로 2로 나눈 나머지가 0 인것들을 체크하여 b를 계속 수정하여 A에 도달하게 만들도록 구현하였고,

 

첫번째 코드는 시간초과, 두번째 코드는 그 문제를 해결한 코드이다. 

 

처음 코드(시간초과)

import sys
input = sys.stdin.readline().strip

a,b = map(int, input().split())
count = 1
while b != a:
    if b < a:
        count = -1
        break

    if (b%10) == 1:
        b = (b//10)
        count += 1
    else:
        if (b%2) == 0:
            b = (b//2)
            count +=1
print(count)

-> A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력하므로 count는 1로 시작하여 b를 다음조건들을 체크하여 B가 두 조건에 맞지 않는 다면 A보다 작아 질 것이라고 생각하고 코드를 짰다. 하지만 여기서 문제가 발생하였다. 너무 예시 테스트 결과만 보고 코드를 짜니, 예시 테스트케이스는 만족을 하지만 그 외의 경우를 체크하지 못하였다.

예를 들어서 어떤 수 B를 계속 나누다가 53에서 멈췄는데 A보다는 클 경우 , 반복문에서 탈출하지 못하고 갇히게 되어 시간초과가 발생된다는 것이다.

 

 

따라서 whlie 문으로 코드를 짤 경우에는 , if elif else 조건으로 예외 상황을 반드시 처리해주어야 한다는 것을 깨달을 수 있었다. 

 

 

두번째 코드(성공)

import sys
input = sys.stdin.readline().strip

a,b = map(int, input().split())
count = 1

while True:
    if a == b:
        break
    elif a > b:
        count = -1
        break
    elif (b%10) == 1:
        b = b//10
        count += 1
    elif (b%2) == 0:
        b = b//2
        count +=1
    else:
        count = -1
        break
print(count)

 

-테이스케이스에 너무 의존하지 말자, 반복문 + 조건시 예외상황이 없나부터 체크해보자.