[백준 4796번] 캠핑

2018. 1. 9. 17:16알고리즘/백준

반응형




풀이


칸을 그려가보면서 생각해보면 되는데 쉽게 풀리지만 백준에서의 입출력 예시만 맞춘다는 생각으로 풀면 틀릴 수 있다.


생각의 순서는 다음과 같다.

1. 나의 휴가는 정해져 있고, 캠핑장을 사용하던 사용하지 않는 기간이 있다. -> 그기간이 P

2. 내가 사용할 수 있는 기간은 L이다.

3. 그렇다면 나의 휴가 V중에 캠핑장을 사용하던 사용하지 않던 허비하는 기간은 총 몇번 반복될까를 파악해보면 V/P이다.

4. 그렇다면 V/P만큼 반복될때 내가 실제로 사용하는 기간은 V/P*L이 된다.

5. 반복한 후 남은 기간은 내가 얼만큼 머물게 될까? -> 나머지를 구하면 된다.

6. 나머지를 구해서 더하면 되지만 나머지가 L보다 크다면 머물수 없는 기간도 포함되어 있다.

7. 그렇다면 나머지를 구해서 두가지로 분리하면 된다.

8. 반복되는 기간을 구한 후 남은 기간 중에서 내가 실제로 머물수 있는 기간과 머물수없는 기간을 나누어서 더한다.


7번에서 예외되는 케이스가 다음과 같다.

백준에서 주어지는 케이스로만 단순하게 계산해보면 

5 8 20 -> (20/8)*5 + (20%8) -> 답 : 10 + 4 = 14

5 8 17 -> (17/8)*5 + (17%8) -> 답 : 10 + 1 = 11

이렇게 나머지 연산만으로 되는줄 알았지만 나머지값이 L보다 커질 수 있다.


예외케이스

5 8 15 -> (15/8)*5 + (15%8) -> 오답 : 5 + 7 = 12

이런 경우 나머지가 7이고, L이 5일 때 오답이 나타나게된다. 즉, L보다 나머지가 더 클경우에는 L만 가지고 연산해야한다.

5 8 15 -> (15/8)*5 + (15%8 > 5 ? 5 : 15%8) -> 답 5 + 5 = 10








소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
 
int main() {
    int a = 1;
    while (1) {
        int L, P, V;
        cin >> L >> P >> V;
        if (!&& !&& !V) { break; }
        int option = (V%P) > L ? L : V%P;
        int result = (V / P)*+ option;
        cout << "Case " << a++ << ": " << result << '\n';
    }
    return 0;
}
cs


반응형

'알고리즘 > 백준' 카테고리의 다른 글