[백준 4796번] 캠핑 - 파이썬

 

문제 링크

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

4796번: 캠핑

 

문제 풀이

• 만약 L = 5, P = 8, V = 20이라고 하면
  강산이의 휴가는 20일이며, 캠핑장은 연속하는 8일 중 5일만 사용할 수 있다.
• 이에 대한 답을 도출해보면...

1-8일 휴가에 캠핑장 5일 이용
9-16일 휴가에 캠핑장 5일 이용
17- 20일 휴가에 캠핑장 4일 이용

     

총 14일 동안 캠핑장을 사용할 수 있다.

• 이를 일반화된 식으로 쓰게 되면
  1~16일 차까지는 (20일 // 8일) * 5일, 
  17~20일 차는 (20일 % 8일)에 해당한다.
  
  즉 (V//P) * L + V%P가 정답이 된다.
  
  
• 하지만 여기서 고려할 점이 있다.
  만약 L이 3, P= 8, V= 20이라고 하면
  정답은 총 9일이 돼야 하는데, 위의 식을 이용하면 10일(3 * 2 + 4)이 도출된다.
  
  이는 L < (V%P)일 때를 고려하지 않았기 때문이다.
  남은 (V%P) 4일 중에 캠핑장을 4일이 아닌 3일(L)밖에 못 간다.
• if문을 이용해 L == V%P임을 적용시켜주면 된다.

이 문제는 그리디 알고리즘 문제로 정해진 규칙을 찾아 식을 만들어 풀 수 있다.

 

풀이 코드

# 4796번 캠핑

# 케이스 횟수
i = 0

# 정답 리스트 생성
ans_data = []

while True:
  i += 1
  l, p, v = map(int, input().split())
  
  # l, p, v 값이 모두 0이라면 실행 종료
  if (l == 0) & (p == 0) & (v == 0):
    break
  
  r = v%p
  # r이 l보다 크다면 r을 l로 채택
  if l< r:
    r = l
  
  ans = (v//p)* l + r
  
  ans_data.append(ans)
  
# 한줄씩 입력받아 답 호출
for k in range(len(ans_data)):
  print('Case %d: %d'%(k+1, ans_data[k]))

 

 

4796번 캠핑 파이썬