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 (!L && !P && !V) { break; } int option = (V%P) > L ? L : V%P; int result = (V / P)*L + option; cout << "Case " << a++ << ": " << result << '\n'; } return 0; } | cs |
'알고리즘 > 백준' 카테고리의 다른 글
[백준 5554번] 심부름 가는 길 (0) | 2018.01.10 |
---|---|
[백준 2098번] 외판원 순회 (0) | 2018.01.09 |
[백준 10799번] 쇠막대기 (0) | 2018.01.05 |
[백준 10798번] 세로읽기 (0) | 2018.01.02 |
[백준 10974번] 모든 순열 (0) | 2017.12.26 |