9. 백준 코딩테스트 4796번 문제 python

이제부터 Greedy Algorithm을 중점으로 풀어보도록 하겠다. 정답률은 39.1%정도이다.

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

4796번: 캠핑

 

들어가기 전.

 

 

그리디(Greedy) 알고리즘은 최적의 해를 구하기위해 사용되는 알고리즘 중 하나로, 여러가지 경우 중 하나를 선택해야할 상황이 올때 그 순간에 최적인 것만 선택해 나가는 방식을 진행하여 최종적인 해답에 도달하는 알고리즘이다.

 

 

해결방법.

 

 

문제를 분석해보자.

P일 중 L일을 사용할 수 있고, V일짜리 휴가를 사용할 때 최대 며칠을 사용하는지 구하는 문제이다.

P와 V의 관계범위를 나누어서 생각해보자.

 

1. V(총 휴가일) < P(캠핑 기준일)인 경우, L(캠핑 최대 이용일수)일을 사용할 수 있다. 다만, V(총 휴가일) < L(캠핑 최대 이용일수)이라면 V(총 휴가일)일을 사용할 수 있고, V(총 휴가일) > L(캠핑 최대 이용일수)이라면 L(캠핑 최대 이용일수)일을 사용할 수 있다. 
2. V > P인 경우, (V//P)*L만큼 갈 수 있고, V%P만큼 추가적으로 보낼 수 있다. 다만 V%P가 L보다 큰 경우, L일만 보낼 수 있다.

코딩을 해보자.

##결과가 저장될 리스트
result = []
while True:
    receive_input = list(map(int, input().split()))
    
    ##모두 0이라면 종료
    if sum(receive_input) == 0:
        break
    else:
        l = receive_input[0]
        p = receive_input[1]
        v = receive_input[2]
        
        ##t는 v%p와 l의 관계에 따라 바뀐다.
        t = 0
        ##v%p가 l보다 작은경우, v%p만큼 추가적으로 캠핑을 즐긴다.
        if v%p < l:
            t = v%p
        ##v%p가 l보다 큰경우, l만큼 추가적으로 캠핑을 즐긴다.
        else:
            t = l
        ##결과 저장
        result.append(l*(v//p) + t)

for index, element in enumerate(result):
    print(f"Case {index+1}: {element}")

 

2번의 조건에서 V%P와 L을 비교하는 것을 누락하여 틀렸다.