[백준] 4796번 : 캠핑 – JAVA [자바]

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

4796번: 캠핑

 

---

• 문제

 

 

---

• 문제 풀이

백준 4796번 캠핑은 브론즈 1 난이도의 수학 및 그리디 문제이다. 이 문제에서는 캠핑장을 연속하는 P일 중, L일 동안만 사용할 수 있다. 이때 휴가가 V일일 때 캠핑장을 최대 며칠 동안 사용할 수 있는지 구하면 된다.

 

우선 이 문제에서 주어진 예제들을 한번 살펴보겠다.

 

EX 1) L = 5, P = 8, V = 20

휴가가 총 20일이고 연속하는 8일 동안 캠핑장을 최대 5일 동안 사용할 수 있다. 우선 연속하는 8일 동안 5일을 사용할 수 있으니 이걸 2번 하면 먼저 10일이 된다. 그러면 휴가는 나머지 4일이 남고 이 4일은 L보다 작으니 4일 전부 다 캠핑장을 사용할 수 있다. 따라서 총 14일이 된다.

 

EX 2) L = 5, P = 8, V = 17

휴가가 총 17일이고 연속하는 8일 동안 캠핑장을 최대 5일 동안 사용할 수 있다. 우선 연속하는 8일 동안 5일을 사용할 수 있으니 이걸 2번 하면 먼저 캠핑장을 사용할 수 있는 날은 10일이 된다. 그러면 휴가는 나머지 1일이 남고 이 1일은 L보다 작으니 1일 전부 다 캠핑장을 사용할 수 있다. 따라서 총 11일이 된다.

 

이 문제에서 패턴을 찾을 수 있다. 패턴을 공식화하면 다음과 같다. total은 캠핑장을 최대로 사용할 수 있는 날이라고 하겠다.

 

total = L × (V / P) + (V % P)

 

하지만 이 공식에서 부족한 점이 있다. 바로 L이 (V % P) 보다 작을 수도 있다는 것이다. 예를 들어서 예제 1번을 다시 한번 보겠다. 단, 연속하는 8일 동안 캠핑장을 최대 2일 동안 사용할 수 있다고 해보겠다.

 

EX 3) L = 2, P = 8, V = 20

연속하는 8일을 두 번 경험하니 우선 4일 동안 캠핑장을 이용할 수 있다. 그리고 나머지 4일 동안 2일을 추가로 이용할 수 있으니 총 6일이 된다.

 

여기서 보면 total을 재정의할 수 있다.

 

total = L × (V / P) + Math.min(L, (V % P))

 

이 공식을 이용해서 문제를 풀면 된다. 자세한 코드는 밑에 있다.

 

---

• 코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int i = 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 && p == 0 && v == 0) break;
            int total = l * (v / p) + Math.min(l, v % p);
            sb.append("Case " + i + ": " + total + "\n");
            i++;
        }
        System.out.print(sb);
    }
}