19539번 : 사과나무

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

19539번: 사과나무

 

 

문제

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

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

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

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

 

 

입력

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

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

 

 

출력

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

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Integer.parseInt(br.readLine());
        int sum = 0;
        ArrayList<Integer> al = new ArrayList();
        StringTokenizer st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            int i = Integer.parseInt(st.nextToken());
            sum += i;
            al.add(i);
        }

        if(sum % 3 != 0) System.out.println("NO");
        else {
            int count = 0;
            for (int i : al) {
                count += i / 2;
            }
            if(sum/3 <= count) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}

 

 

해결방법

혼자 문제를 풀지 못 하고 문제를 푼 다른 블로거분의 해설을 보고 이해하였다.

문제는 1만큼 자라게 하는 물과 2만큼 자라게 하는 물을 무조건 같이 사용하여 주어진 모든 나무의 길이를 며칠지나야 도달할 수 있으냐 가 핵심이다. 그러면 하루에 3만큼 자라게 해주어야하고 특정일이 도달했을때에는 3*n만큼의 길이가 된다. 

 

따라서 목표 나무길이들의 합이 3의 배수가 아니라면 실패이다. 

 

1과 2는 동일 개수가 쓰인다.

며칠을 부어야 완성되는지 알면 1과 2가 얼마나 쓰이는지 쉽게 알 수 있다.

 

총 나무의 길이 / 3 이 걸리는 일수이고, 

 

따라서 2를 붓는 횟수도 위의 일수와 동일하다. 그런데 여기서 2를 부울수 있는 횟수만 확인하면 되는데 그 이유는 1은 어떤 높이여도 상관없다. 왜냐면 1은 그냥 나무의 길이에 상관없이 줄 수 있기 때문이다.

 

아래 입력을 보자

8
4 4 4 4 4 4 4 4

걸리는 일수가 8(24/3)이라면 2를 붓는 횟수는 최소 8번이 되야한다.(더 넘어도 상관X, 8번만 주면 되므로)

1은 상관쓰지 않아도 된다. 1은 그냥 주면 되니까.

 

따라서 2를 부울수 있는 전체횟수가 일수보다 크거나 같으면 만들 수 있게된다. 

 

결론 

1. 목표 나무길이들의 합이 3의 배수가 아니면 "NO"

2. 걸리는 일수보다 2를 붓는 횟수가 적으면 "NO"

3. 이외 모두 "YES"

 

 

참고

https://xkdlaldfjtnl.tistory.com/66