[백준] 4796번 캠핑

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q4796.java

연속 된 P일중 L일 동안 캠핑장을 사용할 수 있다. 휴가는 총 V일 이다. 최대로 캠핑장을 이용할 수 있는
일수를 출력하여라.

처음 생각

수학이라고 생각해야 할 까 그리디라고 생각해야 할까 어떻게 보던지 간에 둘 다 맞는것 같다. 몫과 나머지를 구해도 상관이 없고, 최대로 라는 조건이 주어졌기 때문에 우선적으로 L일을 사용하고 P-L일을 더해주는 식으로 V일 까지 접근을 해도 된다.

▶ 수학적인 접근은 항상 빠르므로 수학적으로 풀어보았다.

다음 생각

연속하는 P일 중 L일이므로 L일을 다 사용하기 위해서는 우선 P일을 사용해야한다. 따라서 주어진 휴가기간 V일 동안 몇 번의 P일이 있는지 V/P를 이용해서 구해주었다. 1번의 P일동안 L일 사용가능하므로 (V/P)*L로 모든 P일 안에서 L일 동안 이용할 수 있는 수를 구해주었다.

다다음 생각

V/P를 하면 나머지가 있을수도 있고 없을 수도 있다. 연속된 P일 이지만 짤린 P일 인것이다. 따라서 이 나머지는 모두 이용이 가능하다.

▶ 여기서 고려해야 할 점은 나머지가 이용할 일 수 보다 큰 경우이다. 따라서 나머지가 L 보다 작으면 나머지 일수를 모두 이용하면되고, 그 반대라면 이용가능 일 수인 L을 모두 이용해주면 된다.

방안

1) 수학적 풀이

package baekjoon.q1000;
 
import java.util.Scanner;
 
public class Q4796 {
    static int l,p,v;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = 1;
        while(true) {
            l = sc.nextInt(); // L일 동안
            p = sc.nextInt(); // 연속 P일중
            v = sc.nextInt(); // 휴가 V일
            // 0이 들어오면 종료
            if(l==0) break;
            // 최대로 이용할 수 있는 날을 따져주어야하므로
            // 우선 연속 P가 최대 몇 번오나 따져준 후 (v/p)
            // 남은 날 수(v%p)가 이용 가능일 L 모다 작으면 전부 이용 아니라면 L 만큼만 이용한다.
            System.out.println("Case "+tc+": "+((v/p)*l+Math.min(l,v%p)));
            tc++;
        }
    }
}
 

2) 그리디 풀이

package baekjoon.q1000;
 
import java.util.Scanner;
 
public class Q4796_Greedy {
    static int l,p,v;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = 1;
        while(true) {
            l = sc.nextInt(); // L일 동안
            p = sc.nextInt(); // 연속 P일중
            v = sc.nextInt(); // 휴가 V일
            // 0이 들어오면 종료
            if(l==0) break;
            // 그리디로 접근해 보자.
            int result = 0;
            // 우선 v일 동안 진행이된다.
            for(int i=0;i<v;) {
                // l일을 사용해준다.
                result += l;
                // l일을 증가시켜준다.
                i += l;
                // v일 을 초과하면 그만큼 빼준다.
                if(i>=v) result -= i-v;
                // P-L일을 더해준다.
                i+=p-l;
            }
            System.out.println("Case "+tc+": "+result);
            tc++;
        }
    }
}