[Kotlin, S4] 백준 20363번 당근 키우기

출처: unsplash.com

 

당근 키우기(20363번)

Silver 4

#수학 #그리디 알고리즘

 

문제 링크

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

 

문제 내용

 

문제 접근

햇빛과 수분을 줄 수 있을 때, 한 항목에 10을 주면 다른 항목이 1이 감소할 때 x, y를 정확히 맞추는 합의 최솟값을 구한다.

 

예제 2를 기준으로 설명하자면,

온기(x)는 123456만큼, 수분(y)은 12345만큼 필요하게 된다.

그러면 최소 123456 + 12345 만큼은 햇빛, 물을 주는 횟수가 필요해지게 된다.

 

123456 + 12345만으로는 x, y를 모두 채울 수가 없다.

햇빛을 먼저 채운다고 가정하면

 

1. sun = 123456, water = 0 

2. sun = 122222, water = 12345

의 상태가 되게 된다.

 

sun이 12345 / 10 만큼 빠져나갔다.

그러면 sun을 123456에서 12345 / 10만큼 추가로 채워주게 되면 나중에 water를 한 번에 받게 되었을 때, x와 값이 같아지게 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val (x, y) = bf.readLine().split(" ").map { it.toInt() }

    println(x + y + min(x, y) / 10)
}

 

문제 풀이

한쪽이 0일 때 감소되는 게 없기 때문에 단순히 더 큰 쪽을 먼저 채우는 방식으로 해결할 수 있다.

x + y + min(x, y) / 10

의 공식으로 문제를 해결할 수 있다.

 

 

문제 해결 과정

처음에는 sun, water를 x, y만큼 채워가면서 횟수를 구해봤는데 정답과 일치하지 않았다.

그래서 풀이를 보고 무조건 x 또는 y만큼 채우기 않고 추가로 더 채울 수 있다는 힌트를 얻을 수 있었다.