문제
정수 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)
'알고리즘 > python' 카테고리의 다른 글
[python/파이썬] 백준 21758 꿀 따기 (0) | 2022.03.22 |
---|---|
[python/파이썬] 백준 21314 민겸수 (0) | 2022.03.21 |
[python/파이썬] 백준 20365 블로그2 (0) | 2022.03.17 |
[python/파이썬] 백준 1541 잃어버린 괄호 (0) | 2022.03.16 |
[python/파이썬] 백준 1931 회의실 배정 (0) | 2022.03.16 |