문제

4796 - 캠핑

접근

그리디 문제이다.

연속하는 P일 중에 L일은 캠핑을 할 수 있다.

즉, P일 중에 캠핑을 한 날이 L일을 넘지않으면 무조건 캠핑을 하는게 이득이다.

이에 따라 전체 휴가인 V일을 P일로 나눈 몫을 a라고 할 때, a*L일은 확정적으로 캠핑을 할 수 있는 날이다.

문제에서 주어진 예시인 5, 8, 20으로 보면

20일을 8로 나눈 몫은 2이다.

8일씩 진행되는 프로세스를 풀타임으로 2번 가질 수 있단 의미이고, 8일 중에 5일은 캠핑이 가능하니, 2*5 = 10,

즉, 16일 중에 최대 10일은 캠핑이 가능하다는 의미이다.

이제 나머지를 어떻게 처리할까?

나머지는 4가 남았다.

이 4일은 연속해서 캠핑 가능한 5일보다 작다.

따라서, 4일은 모두 캠핑을 해도된다.

즉, 10+4=14일동안 캠핑을 할 수 있다.

그럼 나머지가 연속해서 캠핑 가능한 일보다 크면 어떻게 할까?

예를들어 5, 8, 23이라고 하자.

몫은 똑같다.

나머지가 7인데, 이는 5보다 크다.

이 경우 5일을 캠핑하고 나머지 2일은 캠핑을 못한다.

즉 10+5=15일 캠핑이 가능하다.

이를 수식으로 나타내면, (v // p) * l 에

l if v % p >= l else v % p 이 결과를 더하면 된다.

코드

• 파이썬 코드

1
2
3
4
5
6
7
8
9
10
11
12

case = 0
while True:
    case += 1
    l, p, v = map(int, input().split())
    if l+p+v:
        full_time = (v // p) * l
        rem = v % p
        rem = l if rem >= l else rem
        ans = full_time + rem
        print('Case {0}: {1}'.format(case, ans))
    else:
        break