백준 23323 - 황소 다마고치 (자바 - 그리디)

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

23323번: 황소 다마고치

 

* 문제 요약

황소 다마고치는 작은 기계 안에서 황소를 애완동물로 키울 수 있는 장난감이다. 황소에게는 "체력" 수차기 존재하기 때문에, 잊지 말고 꼬박꼬박 먹이를 줘야 한다.

- 매일 낮에 황소에게 원하는 만큼 먹이를 줘 그만큼 체력을 올릴 수 있다. 즉, (0 <= x <= 현재 가지고 있는 먹이의 갯수) 를 만족하는 정수 x 를 고른다. 가지고 있는 먹이의 수가 x 만큼 감소하고, 황소의 체력이 x 만큼 증가한다.

- 매일 밤에 황소의 체력이 절반으로 줄어든다. (나눈 후 소수점 이하는 버린다.) 만약 체력이 0 이 되었다면 황소는 죽고만다.

문제는 가지고 있는 먹이는 한정되어 있다는 것이다. 과연 현재 가진 먹이로 황소가 최대 며칠째까지 생존이 가능할까?

 

* 입력

첫 번째 줄에 테스트 케이스의 갯수 T (1 <= T <= 1,000) 가 주어진다.

다음 T개의 줄에 걸쳐서 황소의 초기 체력을 나타내는 정수 n 과, 현재 가지고 있는 먹이의 갯수 m 이 주어진다.(1 <= n, m <= 10^12)

 

* 출력

T개의 줄에 걸쳐 주어진 순서대로, 황소를 가장 오래 살릴 수 있는 방법으로 먹이를 주었을 때 며칠째 밤에 죽게 되는지 출력한다.

입력, 출력의 값이 32비트형 정수 (C/C++ 의 int) 의 최대값을 넘을 수 있음에 주의하자.

 

* 예시

 

* 해결 과정

초기에 주어진 황소의 체력을 최소 1 까지 깎은 뒤 남아있는 모든 먹이들을 매일 마다 1개씩 주는 방식으로 하면 2 -> 1 -> 2 -> 1 과 같은 루틴을 반복하며 황소가 가장 오래 살아남아 있게 된다.

그러므로 정답은 초기 황소의 체력에서 0 으로 만드는데 걸리는 반복 횟수 + 입력으로 들어온 먹이의 총 갯수이다.

 

* 코드

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 NumberFormatException, IOException {
        new Main().solution();
    }

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

        int tc = Integer.parseInt(br.readLine());

        long result = 0;
        for (int i = 0; i < tc; i++) {
            String[] input = br.readLine().split(" ");
            long health = Long.parseLong(input[0]);
            long feed = Long.parseLong(input[1]);

            while (health >= 1) {
                health /= 2;
                result++;
            }
            bw.write(result + feed + "\n");
            result = 0;
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 초기 황소의 체력이 0 이 될 때까지 반복을 통해 체력을 매 단계마다 계속 절반씩 줄여 준 다음, 반복횟수 + 가지고 있는 먹이의 갯수를 출력해준다.

선택된 해답이 조건을 만족하는지 검사한다. -> 위의 로직을 수행할 경우 황소가 최대로 오랫동안 살아남을 수 있는 날짜에 최대한 가까운 값을 얻을 수 있다.

 

위의 과정을 거쳐 문제를 해결하였으므로 그리디 알고리즘 문제에 해당된다.