<콜라 문제> 풀이

문제 설명

( 참고 : 프로그래머스 문제 그대로 가져왔습니다.)

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

 정답은 아무에게도 말하지 마세요.
 콜라 빈 병 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<= b < a <= n <= 1,000,000
• 정답은 항상 Int 범위를 넘지 않게 주어집니다.

입출력 예

a	b	n	result
2	1	20	19
3	1	20	9

 

입출력 예 설명

#2
1. 빈 병 20개 중 18개를 마트에 가져가서, 6병의 콜라를 받습니다. 이때 상빈이가 가지고 있는 콜라 병의 수는 8(= 20 -18 +6)개 입니다.
2. 빈 병 8개 중 6개를 마트에 가져가서 2병의 콜라를 받습니다. 이때 상빈이가 가지고 있는 콜라 병의 수는 4(= 8 - 6 +2)개 입니다.
3. 빈 병 4개 중 3개를 마트에 가져가서 1병의 콜라를 받습니다. 이때 상빈이가 가지고 있는 콜라 병의 수는 2(=4 - 3 + 1)개 입니다.
4. 3번의 교환 동안 상빈이는 9(= 6 + 2 + 1) 병의 콜라를 받았습니다.

 

문제 이해

문제를 읽어보면 결국은 몫과 나머지 문제라 생각했다. n회차에 가지고 있는 나의 [총 빈병의 개수]를 [요구되는 빈병의 수]로 나눈 몫과 나머지로 다음 회차인 n+1회차에서의 총 빈병의 개수 사이의 관계식을 구현해내는 문제라 생각한다. 어찌보면 고등학생 때 수열문제를 푸는 느낌이었다.

 

내 풀이(Good)

내 풀이를 Good이라 판단한 이유는 풀이 채점 결과 (+12점)을 받았기 때문이다. 사실 잘 푼건지는 모르겠다.

풀이과정에서 사용한 변수를 정리하면 다음과 같다.

• bottles : 각 회차에서의 총 빈병의 개수 ( 초기값은 인자로 주어지는 n 값 )
• a : 1번의 교환에 요구되는 빈병의 수
• b : 1번 교환할 때 돌려주는 새로운 콜라의 수
• remainder : 각 회차에서 요구되는 빈병의 수로 나눈 나머지 값. 즉, 이번 회차에서는 개수가 부족하여 교환하지 못한 병의 수이다. 이는 다음 회차에 총 빈병의 수에 포함된다.
• newCoke : 교환한 빈병으로 얻게될 새로운 콜라의 수.

문제는 매 회차 동일한 행동을 반복하기 때문에 반복문을 활용해야 한다 생각했다. 그렇다면 for 또는 while 문을 활용해야 할텐데, 구체적인 index값을 알 수 없기 때문에 while문으로 종료 조건을 걸어주는 것이 좋다고 생각해서 while문을 활용하였다. 풀이는 다음과 같다.

 

class Solution {
    public int solution(int a, int b, int n) {
        int answer = 0;
        int bottles = n;
        int remainder = 0;
        while(!(bottles < a)){
            int newCoke = (bottles / a) * b;
            answer += newCoke;
            remainder = bottles % a;
            bottles = newCoke + remainder;
        }
        return answer;
    }
}

 

주의해야하는 부분은 반복문 내에서 newCoke를 계산할 때 b를 곱해주는 것을 잊지 말아야한다! 예제에서는 b값이 1이어서 실수로 b값을 빼먹어도 문제없이 돌아가지만, b값이 1이 아닌 다른 값인 경우에는 모두 실패하게된다. 주의하자.

 

오늘의 교훈

결국 알고리즘 문제풀이는 난이도가 올라갈수록 수학적인 사고가 많이 필요하다. 단계를 나눠서 사고하는 방법과 적절한 변수 도입, 여러가지 알고리즘 지식 기반 사고 방법을 익히자.