[Kotlin] 백준 2839 : 설탕 배달

문제 링크

2839번: 설탕 배달

---

---

문제 해설

탐욕법으로 풀 수 있는 간단한 수학 문제다. 처음 N kg이 주어지면 먼저 5로 나눈 값을 옮겨야 할 봉지 수에 더하고 나머지를 남겨 놓는다. 여기서 나머지가 0이면 그 값이 즉시 정답이 된다.

 

나머지가 0이 아니라면 반복문으로 포장하지 않은 설탕(=나머지)의 양이 3으로 나누어 떨어질 때까지 계산을 시작한다. 포장하지 않은 설탕이 3으로 나누어 떨어진다면 나눈 값을 옮겨야 할 봉지 수에 더하고 반복문을 종료한다. 나머지가 3으로 나누어 떨어지지 않는다면 5kg 봉지를 하나 풀어서(=옮겨야 할 봉지 수에서 1개를 빼고) 포장하지 않은 설탕에 5kg를 더한 후 다시 3으로 나누어 떨어지는지 검사한다.

 

이 과정을 반복하다가 포장하지 않은 설탕의 양이 N을 초과하게 되면 N kg은 5kg와 3kg으로 정확하게 배달할 수 없는 경우이므로 -1을 출력한다.

---

Code

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    var sugar = n / 5	// 처음에 5kg 봉지에 모두 담음
    var rest = n % 5	// 5kg 봉지에 담고 남은 설탕
    while (rest in 1..n) {	// 남은 설탕이 존재하면서 N kg이하일 때
        if (rest % 3 != 0) {
        // 남은 설탕을 3kg 포대에 정확히 담을 수 없으면 5kg 봉지를 하나 풂
            sugar--
            rest += 5
        } else {
            sugar += rest / 3
            rest = 0
        }
    }
    println(if (rest != 0) -1 else sugar)
}