[level 1] 콜라 문제

문제

오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다.

정답은 아무에게도 말하지 마세요.

콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가?

단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다.

문제를 풀던 상빈이는 콜라 문제의 완벽한 해답을 찾았습니다. 상빈이가 푼 방법은 아래 그림과 같습니다. 우선 콜라 빈 병 20병을 가져가서 10병을 받습니다. 받은 10병을 모두 마신 뒤, 가져가서 5병을 받습니다. 5병 중 4병을 모두 마신 뒤 가져가서 2병을 받고, 또 2병을 모두 마신 뒤 가져가서 1병을 받습니다. 받은 1병과 5병을 받았을 때 남은 1병을 모두 마신 뒤 가져가면 1병을 또 받을 수 있습니다. 이 경우 상빈이는 총 10 + 5 + 2 + 1 + 1 = 19병의 콜라를 받을 수 있습니다.

문제를 열심히 풀던 상빈이는 일반화된 콜라 문제를 생각했습니다. 이 문제는 빈 병 a개를 가져다주면 콜라 b병을 주는 마트가 있을 때, 빈 병 n개를 가져다주면 몇 병을 받을 수 있는지 계산하는 문제입니다. 기존 콜라 문제와 마찬가지로, 보유 중인 빈 병이 a개 미만이면, 추가적으로 빈 병을 받을 순 없습니다. 상빈이는 열심히 고심했지만, 일반화된 콜라 문제의 답을 찾을 수 없었습니다. 상빈이를 도와, 일반화된 콜라 문제를 해결하는 프로그램을 만들어 주세요.

콜라를 받기 위해 마트에 주어야 하는 병 수 a, 빈 병 a개를 가져다 주면 마트가 주는 콜라 병 수 b, 상빈이가 가지고 있는 빈 병의 개수 n이 매개변수로 주어집니다. 상빈이가 받을 수 있는 콜라의 병 수를 return 하도록 solution 함수를 작성해주세요.

 

 

문제 풀이 접근법1

1) n(상빈이가 가지고 있는 빈병의 개수)이 a보다 작으면 더 이상 교환을 진행할 수 없으므로 n>=a동안 반복문을 진행한다.

2) 만약 n을 a로 나눈 나머지가 0이면 n//a * b(빈 병 n를 냈을 때 돌려 받을 수 있는 콜라의 개수)를 bottle리스트에 추가한 뒤, n을 업데이트 한다(n개를 내고 n/a*b개를 받았으므로 n = n/a * b로 업데이트 된다.)

3) 만약 n을 a로 나눈 나머지가 0으로 떨어지지 않는다면 나머지를 remainder에 추가한 뒤, 다시 n을 업데이트 한다.

4) 또한 n이 a보다 작을 경우에도 (일단은) remainder에 추가한다.

5) remainder의 수(나누어 떨어지지 않아서 잠시 빼둔 빈병 + 가지고 있는 빈병)를 다 더한 값이 n(현재 빈병)보다 크다면 n을 remainder들의 합으로  변경한 뒤, remainder함수 안의 원소를 다 삭제한다. (무한 루프에 빠지는 것을 방지하기 위해)

def solution(a, b, n):
 

    bottle = []
    remainder= []
    answer = 0

    while n >= a:
    
        if n % a == 0:
            n = n // a * b
            bottle.append(n)
        
        else:
            remainder.append(n % a)
            n = n // a * b 
            bottle.append(n)
    
        if n < a:
            remainder.append(n)
    

        if sum(remainder) >= n:
            n = sum(remainder)
            remainder.clear()
        

    
    for i in bottle:
        answer += i


    return answer

1, 3, 6, 9, 12번 테스트 케이스에서 실패했다. 

반례를 찾아보았다. 무조건 작을 때에만 킵해두었던 보틀을 가져오는 것이 아닌, n이 나누어 떨어지지 않을 때도 해야 한다는 걸 알았다. 

 

 

문제 풀이 접근법2

remainder의 sum값이 n보다 클 때가 아니라, n이 a보다 작으면 reaminder의 sum값을 더해줘야 했다. 

해당 부분을 수정하여 해결하였다. 접근법1에서는 반례도 잘못 접근한듯

def solution(a, b, n):
 

    bottle = []
    remainder= []
    answer = 0

    while n >= a:
    
        if n % a == 0:
            n = n // a * b 
            bottle.append(n)
    
        else:
            remainder.append(n % a)
        #print(remainder)
        
            n = n // a*b
            bottle.append(n)
    
        if n < a:
            n = n+sum(remainder)
        #bottle.append(n)
            remainder.clear()
    

    for i in bottle:
        answer += i

    return answer

 

 

다른 분들 풀이

def solution(a, b, n):
    answer = 0
    while n >= a:
        answer += (n // a) * b
        n = (n // a) * b + (n % a)
    return answer

우와 그냥 바로 answer에 더해주고, n을 n //a * b + (n/a)로 해줘도 되는구나!

굳이 리스트를 두개나 사용할 필요가 없었다니

아직 더 고민해보는 습관을 길러야할 것 같다.