Greedy_13_A->B(16953)
Greedy_12_A->B(16953)
문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
풀이
- 조건식 돌때마다 cnt 값 누적
- B 가 A와 같아져야 한다. B의 끝수가 1일땐 [-1]인덱스만 빼고 string 을 재 초기화
- B 가 2로 나뉘어 떨어질 땐 B를 2로나눈 몫으로 초기화
- B의 끝수가 홀수라 나뉘어 질 수 없을때는 -1 출력, 시스템 종료
- B가 A보다 작아지면 어떤 계산으로든 A와 같아질 수 없으므로 -1 출력, 시스템 종료
따라서 조건은 아래와 같다
while 문을 돌린다 조건은 A와 B가같은 경우 종료
같아지려는 수보다 작아진 경우 if int(B) < int(A):exit()
끝이 1인 경우 string 초기화 elif int(B[-1]) == 1:B = str(int(B) // 2)
2로 나뉘어지는 경우 B를 몫으로 초기화 elif int(B) % 2 == 0:B = str(int(B) // 2)
그 외 홀수의 경우 2로 나뉘어 질 수 없으므로 종료else: exit()
코드
import sys
sys.stdin = open("input.txt","rt")
def input():
return sys.stdin.readline().rstrip()
A, B = input().split()
cnt = 1
while B != A:
#같아지려는 수보다 작아진 경우
if int(B) < int(A):
print(-1)
exit()
elif int(B[-1]) == 1:
cnt+=1
# 맨 뒤 값 뺀 수로 초기화
B = B[:len(B)-1]
elif int(B) % 2 == 0:
cnt+=1
B = str(int(B) // 2)
else:
print(-1)
exit()
print(cnt)
배운 것
str 을 [n:m] 으로 slice 할 수 있구나
코멘트
조건식은 항상 else 의 경우도 생각해라
시간초과 난 이유, else를 잡지 못했기 때문
Author And Source
이 문제에 관하여(Greedy_13_A->B(16953)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@angel_eugnen/Greedy12A-B16953저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)