백준 23351 - 물 주기 (자바 - 그리디)

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

23351번: 물 주기

 

* 문제 요약

고양이들이 좋아한다는 캣닢을 직접 재배하려고 한다.

일직선으로 놓여진 N 개의 화분에 캣닢이 하나씩 심어져 있다.

각 화분은 초기에 K 만큼의 수분을 머금고 있고, 매일 아래와 같은 일이 순서대로 일어난다.

1. 연속된 A 개의 화분에 물을 준다. 이 때 물을 준 화분의 수분은 B 만큼씩 증가한다.

2. 모든 화분의 수분이 1 씩 감소한다.

3. 수분이 0 이 된 화분에 있는 캣닢은 죽는다.

 

모든 캣닢이 살아있는 기간이 최대한 길어지도록 물을 줄 때, 첫 캣닢이 죽는 날짜를 출력하는 프로그램을 작성하시오.

첫 날은 1일이다.

 

* 입력

첫째 줄에 자연수 N, K, A, B 가 공백을 사이에 두고 주어진다.

(2 <= N <= 100, 1 <= K <= 100, 1 <= A x B < N, A 는 N의 약수)

 

* 출력

모든 캣닢이 살아있는 기간이 최대한 길어지도록 물을 줄 때, 첫 캣닢이 죽는 날짜를 출력한다.

 

* 예시

 

* 해결 과정

매일 전체 화분중에서 현재 머금고 있는 수분이 가장 적은 순서대로 A 개의 화분에 B 만큼의 수분을 주고 난 뒤, 전체 화분의 수분을 1 씩 감소시키고 나서 현재까지의 반복횟수를 계산하는 변수의 값을 1 증가시키는 방식으로 반복문을 수행한다.

최종적으로 수분을 가장 적게 머금고 있는 화분이 현재 머금고 있는 수분의 수치가 0 이 될 경우 반복문을 종료하고 여태까지 수행되었던 반복 횟수를 출력시키는 방식으로 문제를 풀었다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");

        int result = 0;
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);
        int a = Integer.parseInt(input[2]);
        int b = Integer.parseInt(input[3]);

        int[] potArray = new int[n];
        for (int i = 0; i < potArray.length; i++) {
            potArray[i] = k;
        }

        while (potArray[0] > 0) {
            for (int i = 0; i < a; i++) {
                potArray[i] += b;
            }

            for (int i = 0; i < potArray.length; i++) {
                potArray[i] -= 1;
            }

            Arrays.sort(potArray);
            result++;
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 매 반복마다 수분을 가장 적게 머금고 있는 화분들에 우선적으로 물을 주고, 전체 화분의 수분을 1 씩 감소시킨다.

선택된 해답이 조건을 만족하는지 검사한다. -> 전체 화분의 수분을 1 씩 감소시킨 다음 특정 화분의 수분이 0 이 되었는지 검사하고, 0 이 되지 않았을 경우 계속 반복문을 수행한다.

 

위와 같은 과정을 거쳐 반복문을 끝낸 결과, 최초로 특정 화분의 수분이 0 이 되는 날짜에 최대한 가까운 근사값을 구할 수 있었으므로 그리디 알고리즘에 해당된다.