[백준] 25418 정수 a를 k로 만들기

https://www.acmicpc.net/problem/25418

문제 분석

[ 문제 설명 ]

입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다.

• 연산 1: 정수 A에 1을 더한다.
• 연산 2: 정수 A에 2를 곱한다.

정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자.

[ 입력 ]

첫 번째 줄에 양의 정수 A와 K가 빈칸을 사이에 두고 순서대로 주어진다.

[ 출력 ]

첫 번째 줄에 양의 정수 A를 양의 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력한다.

• 제한
  • 1 ≤ A < K ≤ 1,000,000

---

입출력 예

코드

#연산 1 => 1을 더하기
#연산 2 => 2를 곱하기
A, K = map(int, input().split())
count = 0
while True:
    if A == K: #목표가 되었을 때 계산 멈춘다
        print(count)
        break
    else:
        if K % 2 == 0 and K >= A*2: #2로 나눌 수 있을 때(짝수) + K가 A보다 작아질 때까지만 연산을 수행
            K = K//2
            count +=1
        else:
            K = K-1
            count +=1

문제 풀이 과정

최소 연산 횟수

1을 더하는 것 vs 2를 곱하는 것 → 후자를 해야 최소 연산 횟수

⇒ 욕심내서 2를 곱하는 연산을 할 수 있을 때 더 많이 하자!

첫번째 시도

A, K = map(int, input().split())
count = 0
while A != K:
    # 2를 곱하는 연산을 먼저 수행 
    if A * 2 <= K: #곱해서 특정 수가 안넘어가는 경우만
        A = A * 2
    # 그 다음 1을 더하는 연산
    else:
        A = A + 1
    count += 1

print(count)

⇒ 최소 연산이 안나옴 😭

• 왜그럴까? → “그리디 알고리즘의 정당성”
  • 간단한 예제를 생각해보자!
  • 거스름돈 문제에서 그리디로 풀면 되는데가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
  • 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출 할 수 있다.
  • 500원, 100원, 50원, 10원 동전으로 거스름돈을 주는 경우, 단순히 가장 큰 화폐 단위부터 주면된다. 하지만 배수가 아닌 경우 (→ 500원, 300원, 50원인 경우는) 항상 좋은 것만 선택해서 최적의 답을 도출할 수 없다. 그리디 알고리즘으로는 (500원 1개 + 50원 2개)를 거슬러 주는 동전 총 3개가 나오는데 최적의 해는 (300원 + 300원)을 거슬러 주는 것이기 때문이다.
  • 이 문제의 경우도 특정 숫자에 도달할 때 1을 더해서 만드는 것과 2를 곱해서 만드는 것 2가지 경우가 있으므로 무조건 2를 곱해나가는 것은 최소한의 연산을 구하는 데 적합하지 않다고 할 수 있다.
• 2를 언제 곱하느냐에 따라서 연산 횟수가 달라진다.
• 1을 더하는 연산과 2를 곱하는 연산 중 어떤 것을 먼저 수행해야 할지 판단하고 선택해야함
  • 우선, 2를 곱하는 것이 더 빨리 도달함
  1. K가 짝수이면 2로 나눈다. (원래 문제의 2를 곱하는 연산의 역)
  2. K가 홀수이면 1을 뺀다. (원래 문제의 1을 더하는 연산의 역)
• 짝수이면서 K >= A*2 조건 추가
  • 짝수더라도 2로 나눈 후 결과가 목표 K값보다 작은 결과가 나올 수 있으므로 체크