[JAVA | 백준 4796] 캠핑

백준 4796번 문항 www.acmicpc.net/problem/4796

풀이

그리디 알고리즘 문제이다.

전체 V일짜리 휴가 중 연속하는 P일을 주기로 한다. 예를 들어, 8일(P) 중 5일(L) 캠핑장 이용이 가능하다고 할 때, 그리디 알고리즘에 따라 전체 20일(V) 휴가를 연속 8일 기준으로 나누어 생각한다.

여기서 중요한 것은 남은 날짜이다. 20일 / 8일 의 나머지는 4일인데 이 경우 L 값보다 작거나 같으면 그 나머지를 모두 캠핑장 이용일자로 더해주면 된다. 하지만! 남은 일자가 P와 L 값의 사이 인 경우도 고려해 줘야 한다.

마지막 경우는 0 0 0 값이 주어지므로 0 값이 주어지면 계산을 종료할 수 있도록 작성한다.

import java.util.Scanner;

public class greedy_4796 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int no = 0;

        out:

        do {

            no++;

            int l = sc.nextInt();

            int p = sc.nextInt();

            int v = sc.nextInt();

            if(l==0) break out;

            int cnt = 0;

            int how = (v%p<=l) ? v%p : l;

            cnt = v/p*l + how;

            System.out.println("Case "+ no +": "+cnt);

        } while(true);

}

}

Comments