[자바]백준 4796번 캠핑 [그리디][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

그리디 알고리즘이란!?

Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다.
탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

문제

등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다.

캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다.

강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가 기간 동안 강산이는 캠핑장을 며칠동안 사용할 수 있을까?

강산이는 조금 더 일반화해서 문제를 풀려고 한다. 

캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠동안 사용할 수 있을까? (1 < L < P < V)

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다.

출력

각 테스트 케이스에 대해서, 강산이가 캠핑장을 최대 며칠동안 사용할 수 있는지 예제 출력처럼 출력한다.

 

입출력 예제

알고리즘 분류

• 수학
• 그리디 알고리즘

문제 설명

강산이가 28(V)일간 휴가가 생겨서 캠핑장에 놀러갔는데, 캠핑장은 20일(P) 중에 10일(L)만 이용 가능하다.

이 말은 즉 캠핑장 연속된 일수 1일 ~ 20일 중에 딱 10일만 사용 가능하며, 10일간 사용했으면 그다음 연속한 일수 21일 ~40일에 또 10일 사용할 수 있다는 말이다.

해설

이 문제는 그리디보다도 그냥 수학적으로 접근하면 쉽게 풀린다.

위의 문제에서 나온 데이터로 설명해보겠다. (참고. 여기서 말하는 1일 ~ 20일은 일수를 말하는거지 한달 개념이 아니다.)

 

• 캠핑장 1일 ~ 20일 중 10일을 휴가로 보낼 수 있다.
  •  28일중 20일이 사라지며, 10일간 캠핑장에 있고 휴가는 8일 남았다.
• 캠핑장 21일 ~ 40일 중 10일을 휴가로 보낼 수 있다.
  • 강산이의 남은 휴가는 8일이라 캠핑장에 8일동안만 머물렀다.
• 총 18일을 캠핑장에 머물렀다.

이것을 수학적으로 계산 해보면 아래와 같다.

• 강산이의 휴가(V) / 캠핑장 연속된 일(P) * 가능일(L) + 나머지 강산이의 남은 휴가(단 L이하만 가능)

L이하만 가능한 이유는 아래와 같다.

(단, 강산이가 31(V)일간 휴가라고 가정해보자.)

• 캠핑장 1일 ~ 20일 중 10일을 휴가로 보낼 수 있다.
  •  28일중 20일이 사라지며, 10일간 캠핑장에 있고 휴가는 11일 남았다.
• 캠핑장 21일 ~ 40일 중 10일을 휴가로 보낼 수 있다.
  • 강산이의 남은 휴가는11일이다.
  • 캠핑장에서 보낼 수 있는  시간은 10일 뿐이라 10일간 캠핑장에 있었다.
  • 나머지 1일은 다음 캠핑장 41일 부터 가능하다.
  • 41일 부터는 이미 강산이의 휴가를 초과하여 남은 1일은 캠핑장에 머무를 수 없다.
• 총 20일을 머물렀다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int idx = 1;
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int L = Integer.parseInt(st.nextToken());
            int P = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            
            if (L == 0) {
                break;
            }
            
            int useDay = V / P * L + Math.min(L, V % P);
            
            bw.write("Case " + idx++ + ": " + useDay + "\n");
        }

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