[백준 4796번: 캠핑] 파이썬 풀이_그리디 알고리즘

4796번: 캠핑

문제

 

등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다.

캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다.

강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가 기간 동안 강산이는 캠핑장을 며칠동안 사용할 수 있을까?

강산이는 조금 더 일반화해서 문제를 풀려고 한다. 

캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠동안 사용할 수 있을까? (1 < L < P < V)

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다.

출력

각 테스트 케이스에 대해서, 강산이가 캠핑장을 최대 며칠동안 사용할 수 있는지 예제 출력처럼 출력한다.

---

풀이

i = 1
while True:
  a = list(map(int, input().split()))  # 입력 받은 값을 a라는 리스트에 넣음
  if (a == [0, 0, 0]):  # 입력을 [0, 0, 0]이 들어오기 전까지 받음
    break
  if (a[2]%a[1] < a[0]): 
    result = str((a[2]//a[1])*a[0] + a[2]%a[1])
  else:
    result = str((a[2]//a[1])*a[0] + a[0])
  print ("Case "+ str(i) +": "+ result)
  i += 1

---

💡 Challenge

첫 번째 시도 (잘못된 풀이)

예) 8일 중 5일을 사용할 수 있고, 총 20일이라고 했을 때, 20에서 8을 나눈 몫*5일 + 20에서 8을 나눈 나머지로 계산하면 된다고 생각함

→ 입력받은 세 수를 a = [5, 8, 20] 형태로 리스트에 넣고 (a[2]//a[1])*a[0] + a[2]%a[1]

 

i = 1
while True:
  a = list(map(int, input().split()))  # 입력 받은 값을 a라는 리스트에 넣음
  if (a == [0, 0, 0]):  # 입력을 [0, 0, 0]이 들어오기 전까지 받음
    break
  result = str((a[2]//a[1])*a[0] + a[2]%a[1])
  print ("Case "+ str(i) +": "+ result)
  i += 1

 

→ 틀렸습니다

 

반례 찾기

ex) [1, 4, 7]

 

4일 중 1일이 가능하고 7일이면 총 2일이 가능

 

But (a[2]//a[1])a[0] + a[2]%a[1]로 계산하면 7//41+3이 되므로 값이 4가 됨

a[2]%a[1]이 a[0] 보다 클 때는 a[2]%a[1] 자리에 a[0]을 더해주어야 함!

→ if문으로 코드 수정

 

i = 1
while True:
  a = list(map(int, input().split()))  # 입력 받은 값을 a라는 리스트에 넣음
  if (a == [0, 0, 0]):  # 입력을 [0, 0, 0]이 들어오기 전까지 받음
    break
  if (a[2]%a[1] < a[0]):  # if문 추가
    result = str((a[2]//a[1])*a[0] + a[2]%a[1])
  else:
    result = str((a[2]//a[1])*a[0] + a[0])
  print ("Case "+ str(i) +": "+ result)
  i += 1

---

그리디 알고리즘이란?

**그리디 알고리즘(탐욕 알고리즘, Greedy Algorithm)**은 각 단계에서 현재 상황에서 가장 최선으로 생각되는 선택을 하면서 문제를 해결하는 알고리즘이다. 이 선택은 그 순간에는 지역적으로 최적일 수 있지만, 이러한 선택들이 모여 전체적으로 최적해를 보장하지는 않을 수 있다. 그리디 알고리즘은 현재 상황에서의 최적의 선택을 반복하면서 문제의 해답을 찾아나간다.

 

그리디 알고리즘 동작 방식

1. 선택: 각 단계에서 현재 상황에서 가장 최선으로 보이는 선택을 하고 이를 해답에 추가한다.
2. 유효성 검사: 선택된 해답을 기존 문제에 대입하여 문제의 조건을 만족하는지 검사한다.
3. 해결 또는 조정: 선택된 해답이 문제를 충분히 해결하지 못하거나 유효하지 않다면, 조금씩 조정하거나 적절한 변화를 주면서 다시 처음부터 시작한다.