백준 20363 - 당근 키우기 (자바 - 그리디)

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

20363번: 당근 키우기

 

* 문제 요약

씨앗이 X 만큼의 온기와 Y 만큼의 수분을 가지면 당근으로 자란다.

햇빛을 1번 받을 때마다 1 만큼의 온기가 증가하고, 햇빛을 10번 받을 때마다 1 만큼 수분이 감소한다.

물을 1번 받을 때마다 수분이 1 만큼 증가하고, 물을 10번 받을 때마다 1 만큼 온기가 감소한다.

감소되어야 하는 온기 또는 수분이 0 이라면 감소되지 않는다. 즉, 온기와 수분은 음수가 되지 않는다.

맨 처음 씨앗의 온기와 수분은 0 이다. 

당근이 자랄때까지 햇빛과 물을 주는 횟수의 합을 최소화 하려고한다.

예를 들어 X = 10, Y = 10 이라고하자.

씨앗에 햇빛을 10번 주면 온기 10, 수분 0 이 된다. 그리고 물을 10번 주면 온기 9, 수분 10이 된다.

마지막으로 햇빛을 1번 주면 온기 10, 수분 10 으로 당근이 자라게 된다.

이때 햇빛과 물을 준 횟수의 합은 21 이고 이는 위 예제에서의 최솟값이 된다.

X 와 Y 가 주어졌을 때 당근이 자랄때까지 햇빛과 물을 주는 횟수의 최솟값을 구하는 프로그램을 작성하라.

 

* 입력

첫째 줄에 X 와 Y (0 <= X, Y <= 10^9) 를 의미하는 정수가 공백으로 구분되어 주어진다.

 

* 출력

당근이 자랄때까지 햇빛과 물을 주는 횟수의 합의 최솟값을 나타내는 정수를 출력하라.

 

* 예시

 

* 해결 과정

위의 예시 중 123456 12345 가 주어졌을 때, 둘의 합산 값 135,801 과 결과 출력값 137,035 의 차이가 1,234 밖에 되지 않는 것을 보고 어째서 이렇게 되는것인지를 고민하다, 온기와 수분 둘 다 작아져봤자 음수가 되지는 않는다는 점을 보고 풀이법을 깨달은 문제

 

둘 중 더 큰값을 먼저 목표치까지 올린다.

그 다음 더 작은 값을 올릴 때 줄어들 값만큼 추가로 더해준다.

(어차피 값이 음수 이하로 줄어들지 않기 때문에 반대쪽이 0 일 때 미리 줄어들만큼을 추가로 더 올려주는 것이다.)

그 다음 반대쪽을 필요한 만큼 주면 정확하게 X, Y 를 맞춰줄 수 있다.

 

* 코드

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

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(" ");

        long number1 = Long.parseLong(input[0]);
        long number2 = Long.parseLong(input[1]);

        long result = 0;
        if (number1 >= number2) {
            result += number1 + number2 + (number2 / 10);
        } else if (number1 < number2) {
            result += number1 + number2 + (number1 / 10);
        }

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

 

두 값중 어느 값이 더 크냐 작냐에 따라 값이 음수로 떨어지지 않는다는 조건을 활용하여 온기와 수분을 주는 횟수를 최소화 시킬 수 있는 로직을 수행하였으므로 그리디 알고리즘 문제에 해당된다.