백준 19539번: 사과나무

문제: https://www.acmicpc.net/problem/19539

문제 풀이

그리디

sum = 나무 높이의 전체 합

list = 나무의 높이가 2 이상인 나무의 리스트

count = 목표 높이를 만들기 위한 두 물뿌리개의 사용 횟수

twoCount = 나무의 높이를 2만큼 성장시키는 물뿌리개의 사용 가능 횟수

sum을 3으로 나눈 나머지가 0이 아니라면 불가능, sum을 3으로 나눈 나머지가 0일 때 count가 twoCount보다 크면 불가능이고 아니라면 가능

풀이 설명

문제 설명에 따라 나무를 1만큼 성장시키는 물뿌리개와 나무를 2만큼 성장시키는 물뿌리개를 동시에 사용해야 한다고 했으므로 물뿌리개를 한번 사용할 때 나무를 총 3만큼 성장시켜야 한다는 뜻이다. 따라서 전체 나무의 높이의 합이 3으로 나누어떨어지지 않는다면 물뿌리개를 사용했을 때 만들 수 없는 높이이므로 불가능하다.

전체 나무의 높이의 합을 3으로 나눈 몫이 물뿌리개를 사용하는 횟수가 된다. 이 횟수만큼 두 물뿌리개를 사용해야 하고 높이를 1만큼 성장시키는 물뿌리개는 원하는 높이보다 작은 나무라면 어떤 나무라도 사용할 수 있지만, 높이를 2만큼 성장시키는 물뿌리개는 원하는 높이와 현재 높이의 차이가 2 이상인 나무에만 사용할 수 있다. 그러므로 2만큼 성장시키는 물뿌리개를 사용할 수 있는 최대 횟수가 물뿌리개를 사용하는 횟수보다 작다면 원하는 높이를 만드는 것이 불가능하다는 뜻이다.

따라서 필요한 나무의 높이가 2 이상인 나무들의 높이를 2로 나눈 몫의 합이 높이를 2만큼 성장시키는 물뿌리개를 사용 가능한 최대 횟수가 되고 이 값이 전체 나무를 목표 높이까지 성장시키기 위한 두 물뿌리개의 사용 횟수보다 작다면 이 높이를 만드는 것이 불가능한 것이다.

전체 나무의 높이의 합이 3으로 나누어 떨어지고 2만큼 성장시키는 물뿌리개를 사용 가능한 최대 횟수가 목표 높이를 만들기 위해 사용해야 하는 두 물뿌리개의 사용 횟수보다 크다면 2만큼 성장시키는 물뿌리개를 목표 높이를 만들기 위해 사용해야 하는 두 물뿌리개의 사용 횟수만큼만 사용하고 나머지 횟수만큼 높이를 1만큼 성장시키는 물뿌리개를 사용해 만들 수 있는 높이이기 때문에 가능한 높이가 된다. 따라서 이 경우에만 YES를 출력하고 나머지는 NO를 출력하면 된다.

소스 코드

import java.util.StringTokenizer

fun main(){
    val N = readLine()!!.toInt()
    var sum = 0
    val st = StringTokenizer(readLine())
    var twoCount = 0
    repeat(N){
        val height = st.nextToken().toInt()
        sum += height
        if(height > 1){
            twoCount += height / 2
        }
    }
    if(sum % 3 == 0){
        var count = sum / 3
        if(count > twoCount){
            println("NO")
        } else {
            println("YES")
        }
    } else {
        println("NO")
    }
}