[백준(BOJ)] 19539 사과나무 - 스위프트(Swift)

[Gold V] 사과나무 - 19539

문제 링크

성능 요약

메모리: 76308 KB, 시간: 48 ms

분류

그리디 알고리즘, 수학

문제 설명

이하는 최근 사과나무 씨앗을 구매하여 농장 뒷뜰에 일렬로 1번부터 N번까지 심었다. 이 나무들의 초기 높이는 모두 0이다.

사과나무를 무럭무럭 키우기 위해 이하는 물뿌리개 2개를 준비했다. 한 물뿌리개는 나무 하나를 1만큼 성장시키고, 다른 물뿌리개는 나무 하나를 2만큼 성장시킨다. 이 물뿌리개들은 동시에 사용해야 하며, 물뿌리개를 나무가 없는 토양에 사용할 수는 없다. 두 물뿌리개를 한 나무에 사용하여 3만큼 키울 수도 있다.

물뿌리개 관리 시스템을 전부 프로그래밍한 이하는 이제 사과나무를 키워보려고 했다. 그 순간, 갊자가 놀러와서 각 사과나무의 높이가 이런 배치가 되었으면 좋겠다고 말했다. 이제 이하는 약간 걱정이 되기 시작했는데, 갊자가 알려준 사과나무의 배치를 이 프로그램 상으로 만들어내지 못할 수도 있기 때문이다.

이하는 이제 프로그램을 다시 수정하느라 바쁘기 때문에, 두 물뿌리개를 이용해 갊자가 알려준 사과나무의 배치를 만들 수 있는지의 여부를 판단하는 과정은 여러분의 몫이 되었다.

입력

첫 번째 줄에는 자연수 N이 주어진다. (1≤N≤100,000) 이는 이하가 뒷뜰에 심은 사과나무의 개수를 뜻한다.

두 번째 줄에는 N개의 정수 h1,h2,⋯,h_N이 공백으로 구분되어 주어진다. (0≤hi≤10 000) hi는 갊자가 바라는 i번째 나무의 높이이다.

출력

첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다.

 

풀이

i)

우선 가장 기본은 나무 길이의 합이 3의 배수여야 한다는 점입니다. 이를 만족하지 않으면 "NO"이고, 그 다음 조건에 대해 생각해보았습니다.

처음에는 2로 나눈 몫의 합과 1의 개수를 비교하여 2로 나눈 몫의 합이 더 많은 경우에 "YES"가 되는 것으로 생각하고 문제를 풀었습니다.

let n = Int(readLine()!)!
let tree = readLine()!.split(separator: " ").map { Int($0)! }
var (sumTree, heightOneTree, devideTwoTree) = (0, 0, 0)

for i in 0..<tree.count {
    sumTree += tree[i]
    if tree[i] == 1 {
        heightOneTree += 1
    }
    if tree[i] >= 2 {
        devideTwoTree += tree[i] / 2
    }
}

if sumTree == 0 {
    print("YES")
} else if sumTree % 3 != 0 {    // 3의 배수가 아닌 경우
    print("NO")
} else {
    if heightOneTree < devideTwoTree {    // 1의 개수가 2로 나눈 몫보다 적을 때
        print("YES")
    } else {
        print("NO")
    }
}

→ 틀렸습니다

 

예를 들어 1 1 1 3 3 3 3인 경우에는 위의 조건을 만족하지만 나무를 생성할 수 없기 때문입니다.

 

ii)

1의 개수랑 비교하는 것이 아니라 3으로 나눈 몫과 비교를 해야합니다.

 

어차피 1은 자유롭게 사용할 수 있기 때문에 2를 기준으로 나눠야함은 위에서도 유추할 수 있었습니다.

3으로 나눈 몫보다 2를 뿌릴 수 있는 날이 더 적다는 것은 1을 뿌리는 날이 더 많다는 것인데,

이는 물뿌리개를 동시에 사용해야 한다는 조건을 위배하게 됩니다.

 

따라서 3으로 나눈 몫보다 2로 나눈 몫의 일수가 더 많거나 같아야 합니다.

 

이를 코드로 구현하면 다음과 같습니다.

let n = Int(readLine()!)!
let tree = readLine()!.split(separator: " ").map { Int($0)! }
var (sumTree, divideThreeTree, divideTwoTree) = (0, 0, 0)

for i in 0..<tree.count {
    sumTree += tree[i]
    if tree[i] >= 2 {
        divideTwoTree += tree[i] / 2
    }
}

divideThreeTree = sumTree / 3

if sumTree == 0 {   // 전체 높이가 0인 경우
    print("YES")
} else if sumTree % 3 != 0 {    // 3의 배수가 아닌 경우
    print("NO")
} else {
    if divideTwoTree >= divideThreeTree {   // 2를 뿌릴 수 있는 날이 총 일수보다 많거나 같다면
        print("YES")
    } else {
        print("NO")
    }
}