[백준 파이썬 2796] 캠핑 (브론즈 1)

https://www.acmicpc.net/problem/4796

4796번: 캠핑

import sys
from collections import deque
input = sys.stdin.readline
case = 1

while True:
    L, P, V = map(int, input().split())
    if L == 0 and P == 0 and V == 0:
        break

    li = [1 if x < L else 0 for x in range(V)]
    for i in range(V - P + 1):
        arr = li[i:i+P]
        if arr.count(1) != L:
            li[i+P-1] = 1

    res = li.count(1)
    print(f"Case {case}: {res}")
    case += 1

** 이거 틀린 코드임 ** 

 

처음에는 이렇게 했다. 먼저 L=5, P=8, V=28 로 할 때,(총 휴가 28일에 연속 8일 중 5일만 캠핑 가능) 28개의 배열을 만드는데 그중 첫 5일은 1로 (캠핑이 가능하다는 뜻), 나머지는 0으로 초기화 했다. 

이후로 [0:8], [1:9], ... , [21:29] 이렇게 21번 반복하여 배열 중 P개 만큼 떼어와서 L개가 아니면 가장 끝자리를 1로 바꿔주었다. 

그러니 메모리 부족 오류가 나더라 ㅎㅎ,, 

 

그런데 가만 생각해보니 5 8 17 (테스트 케이스 2) 로 예를 들면

[ 1 1 1 1 1 0 0 0 ] (0~7)

[ 1 1 1 1 1 0 0 0 ] (8~15)

[ 1 ] (16) 

 

이렇게 규칙이 있어서 이걸 일반화 해보면, 

import sys
input = sys.stdin.readline
case = 1

while True:
    L, P, V = map(int, input().split())
    if L == 0 and P == 0 and V == 0:
        break

    res = (V // P) * L + min(V % P, L)
    
    print(f"Case {case}: {res}")
    case += 1

다음과 같이 된다. 

 

[ 1 1 1 1 1 0 0 0 ] (0~7)

[ 1 1 1 1 1 0 0 0 ] (8~15)

[ 1 ] (16) 

 

이걸 다시 보면, 우선 V를 P개 만큼 배열을 잘라보면 나머지가 생기지 않는 경우엔 (몫으로 떨어지는 경우엔) 패턴이 P 개 중 1이 V개로 똑같다. 그러면 이제 나머지가 있을 경우를 생각해보면 나머지가 L개를 초과하더라도 캠핑은 L일 이상 할 수 없으므로, 나머지와 L 중에 최솟값이 최대 캠핑 횟수인걸 알 수 있다. 

 

L=5, P=8, V=22로 예를 들어보자면, 

[ 1 1 1 1 1 0 0 0 ] (0~7)

[ 1 1 1 1 1 0 0 0 ] (8~15)

[ 1 1 1 1 1 0 ] (16~21) 

 

로 나머지인 6과 L의 5 중 최솟값인 5가 최대 캠핑 횟수다. 

 

따라서 ( V // P ) * L + min( V % P, L) 이 정답이 된다.