[python/파이썬] 백준 16953 A → B

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제 입력 1 복사

2 162

예제 출력 1 복사

5

2 → 4 → 8 → 81 → 162

예제 입력 2 복사

4 42

예제 출력 2 복사

-1

예제 입력 3 복사

100 40021

예제 출력 3 복사

5

100 → 200 → 2001 → 4002 → 40021

 

[풀이 방법]

 

이 문제의 핵심은 A를 B로 만드는 것이 아닌 B를 A로 만드는 것이다.

B를 줄이고 줄여서 A로 만들었을 때 연산 횟수를 알아내는 방법으로 풀어야 한다.

연산의 횟수를 줄이기 위해서는

2를 곱하는 연산보다 끝 자리에 1을 붙이는 게 더 유리하다 -> 10을 곱하고 1을 더하기 때문

 

즉 B를 A로 만들 때는 1을 빼고 10으로 나눠주는 연산이다.

 

따라서 B가 1로 끝나면 (B-1)/10 연산을 해주고

1로 끝나지 않고 2로 나눠지면 B/2 연산을 진행하면 된다.

 

두 연산이 안되면 B는 A가 될 수 없고, A는 B가 될 수 없다

 

[소스 코드 1 - 시간초과]

 

before -> A

after -> B

 

B의 끝자리가 1로 끝나야 한다는 것에 집중하다 보니 B를 string으로 받고, list로 바꾼 다음에 -1번째 원소가 무엇인지 확인하는 방법을 택하게 되었다

다시 봐도 지저분한 코드이다

답은 나오긴 하지만 시간 초과가 나오는 코드이다.

before, after = input().split() #A와 B를 string으로 입력받는다

after_list = list(after) #B를 list의 형태로 저장

count = 1
while int(after) >= int(before): #B가 A보다 더 크거나 같으면 계속 진행 
    if after_list[-1] == '1': #B에서 1의 자리수가 1일 때
        if int(after) >= 11: #그리고 11보다 크거나 같을 때 -> (B - 1)/10 연산이 가능하도록
            tmp = int((int(after) - 1)/10)
            after = str(tmp) #정수를 문자열로 바꾸고
            after_list = list(after) #문자열을 리스트로 바꾼다
            count += 1 #연산의 수를 증가
    elif int(after) % 2 == 0 : #만일 2로 나누어 떨어진다면
        tmp = int(int(after)/2) #2로 나눔
        after = str(tmp)
        after_list = list(after)
        count += 1
    if int(before) == int(after): #만일 B를 연산하고 연산해서 A와 같아졌다면
        print(count) #count값 출력
        break
if int(after) < int(before): #모든 연산이 끝난 후에 B가 A보다 작다는 것은 A로 만들 수 없다는 뜻
    print(-1)

 

 

[소스 코드2 - 맞았습니다]

 

굳이 문자열, 리스트를 사용할 필요 없이 숫자로 깔끔하게 푼 방법이다.

1의 자리가 1이라는 것을 % 연산을 통해서 표현하였다 

(B -1)/10을 //연산자를 통해서 간단하게 나타낼 수 있었다

 

처음에는 while문 때문에 시간 초과가 떴나 했지만 while 없이는 풀 수 없을 것 같아서

잘 짜인 코드를 보니 내 코드는 시간 초과가 뜰 수밖에 없었다.

열심히 해야겠다

before, after = map(int,input().split())

count = 1

while after != before: #A와 B가 같지 않다면 -> 계속 연산을 진행해야 함
    count += 1 #연산의 횟수 증가
    if after == before: #만일 A와 B가 같다면 break
        break
    tmp = after #B의 값을 tmp에 저장
    if after % 10 == 1: #10으로 나눈 값이 1이라면 -> 1의 자리 : 1
        after //= 10 #10으로 나눈 몫을 저장
    elif after % 2 == 0 : #2로 나눠진다면
        after //= 2  #2로 나눈 몫을 저장
    if tmp == after: #만일 연산 전의 값과 현재 값이 동일하다면 연산을 진행할 수 없는 값
        count = -1 
        break
        
        
print(count)