BOJ 20363 - 당근 키우기

문제

백준 온라인 저지 - 20363번

풀이 과정

물과 햇빛을 주는 규칙이 주어질 때 목표 수치로 도달하기 위한 최소 횟수를 구하는 문제입니다.

예시로 햇빛과 물의 목표치가 123456, 12345 일 경우를 생각해보겠습니다.
10 으로 나눈 몫 만큼 반대편 수치가 줄어들기 때문에 첫번째 시도에는 두 수치중 큰 수치를 먼저 만족시키는게 유리합니다.

그런데 이때 123456 을 딱 맞춘 다음 12345 를 만족시키는 경우와
123456 보다 더 많은 수치를 부여한 뒤 12345 를 만족시키는
이 두 가지 경우에서 어떤 것이 더 적은 횟수의 양분 공급을 필요로 할까요?

10 으로 나눈 몫 만큼 반대편 수치가 줄어들기 때문에 첫번째 경우 1234, 123, 12, 1 순서대로 양분 공급이 필요합니다.
즉 첫번째 입력으로 주어지는 X, Y 중 더 작은 수의 자리수를 하나씩 줄여가며 모두 더한 값을 필요로 하는 것입니다.

그런데 처음에 123456 보다 더 많은 수치인 123456 + 1234 만큼 양분을 주면 어떻게 될까요?
이 경우 두 번의 시도만에 목표치에 달성할 수 있으며 총 드는 비용도 적습니다.

이는 각 자리수를 줄여가며 모든 양수를 더하는 것이 항상 크기 때문에 발생하는 것으로 그리디 한 성질을 만족하기 때문에
두 번째 방법으로 양분을 공급하면 항상 최소의 횟수로 당근을 키울 수 있습니다.

코드

import sys

X, Y = list(map(int, sys.stdin.readline().split()))


def solution():
    answer = (X + Y) + Y // 10 if X >= Y else (X + Y) + X // 10

    return answer


print(solution())