백준(Baekjoon Online Judge) - 4796번(캠핑) 문제 풀이

1. 문제

2. 입출력 예시

3. 문제 풀이

주어진 입력/출력 예시를 통해 점화식을 세워보도록 하자. 휴가를 사용할 수 있는 총 기간이 20일이다. 그리고 이 중 연속된 8일은 2번(20 ÷ 8) 존재한다. 캠핌장 사용은 연속된 8일 중 5일만 사용 가능하므로 연속된 2일에 대한 캠핑장 사용 일수는 10일(20 ÷ 8 × 5)이다. 그렇다면 연속되지 않은 나머지 4일은 어떻게 될까? 이 역시 휴가 전과 후에 연속된 또 다른 8일이 존재한다. 즉, 나머지 4일은 캠핑장 사용 가능 일수 5일보다 작으므로 모두 캠핑장 사용이 가능하다. 따라서, Case 1의 캠핑장 사용 가능 총 일수는 14일(10 + 4) 이다. Case 2도 이와 마찬가지로 계산하면 된다.

그러나 위의 조건에서 휴가 일수가 23일인 경우를 가정해보아야 한다. 23일 중 연속된 8일은 마찬가지로 2번(20 ÷ 8) 존재하며, 이 중 캠핑장 사용 가능 일수는 10일(20 ÷ 8 × 5)이다. 그러면 나머지 7일이 남는데 이는 캠핑장 사용 가능 일수 5일보다 크다. 캠핑장 사용 가능 일수는 5일까지 이므로 나머지 7일 중 5일만 캠핑장 사용이 가능하다. 따라서, 이 경우의 캠핑장 사용 가능 총 일수는 15일(10 + 5)이며, 이를 그림으로 표현하면 아래와 같다.

이제 코드를 작성하기 위해 순서를 세워본다.

• 테스트 케이스의 데이터를 담을 리스트(case)를 선언한다.
• while 문을 통해 무한반복(True)을 하며, 테스트 케이스의 데이터를 입력받는다. 이 때, 테스트 케이스의 데이터가 [0, 0, 0]이면 무한루프를 빠져나오고, 그 밖의 경우에는 case에 테스트 케이스의 데이터를 추가한다.
• for문을 통해 리스트에 담긴 테스트 케이스의 데이터를 호출하며, 아래의 내용을 수행한다.
  • 총 캠핑 사용 가능 일수(total)은 휴가 기간(V)에서 연속된 일수(P)를 나눈 몫에 연속된 일수 동안 캠핑장 사용 가능 일수(P)를 곱한 값으로 초기화한다.
  • 만약에 휴가 기간(V)을 연속된 일수(P)로 나누었을때 나머지가 연속된 일수 동안 캠핑장 사용 가능 일수(P)보다 크거나 같을 경우 총 캠핑 사용 가능 일수에 캠핑장 사용 가능 일수(P)만큼만 더하고, 그 외에는 휴가 기간(V)을 연속된 일수(P)로 나눈 나머지를 더한다.
  • 위의 연산이 끝나면 Case {i+1}: {total}형식으로 출력한다.
• 위의 반복이 끝나면 프로그램을 종료한다.

이를 코드로 나타내면 아래와 같다. 이 코드의 메모리는 28,776 KB, 시간은 92 ms가 소요되었다.

case = []

while True:
    test = list(map(int, input().split()))
    if test == [0, 0, 0]:
        break
    else:
        case.append(test)

for i, (L, P, V) in enumerate(case):
    total = V // P * L
    if V % P >= L:
        total += L
    else:
        total += (V % P)
    print(f"Case {i+1}: {total}")

참고자료

• 백준알고리즘 문제 - 4796번 캠핑