나다.
이 글이 뭐하는 글이냐면
프로그래머스라는 사이트에 있는 코딩테스트 연습 문제인 콜라 문제에 대한 풀이와 해석이다.
콜라 문제
오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다.
정답은 아무에게도 말하지 마세요.
콜라 빈 병 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 함수를 작성해주세요.
해답
class Solution {
public int solution(int a, int b, int n) {
int answer = 0;
int empty = n;
while(true){
answer += (empty / a) * b;
empty = (empty % a) + (empty / a) * b;
if(empty < a){
break;
}
}
return answer;
}
}
해당 해답 보다 더 최적화된 답안이 있을 수 있으니 본인의 해답이 더 효율이 좋다면 그것을 사용하길 권장 드린다.
풀이
해당 문제의 핵심은
"빈 병 a개를 가져다주면 콜라 b병을 주는 마트가 있을 때, 빈 병 n개를 가져다주면 몇 병을 받을 수 있는지"
에 있다.
공병 a 개를 가져다줄 때 콜라 b 병으로 바꿔주는 반복적인 과정을 계산하게 되는데 총 2개의 변수를 필요로 한다.
"int answer"의 경우 공병을 콜라로 바꿨을 때 마지노선까지 바꿔 먹는다면 몇 병의 콜라를 가질 수 있냐에
대한 값을 저장해야 하고
"int empty"의 경우 계산에 사용하게 될 공병의 개수를 저장해야 한다.
또한, 최초 가지게 되는 콜라 n 병은 고스란히 공병이 될 예정이므로 empty의 초깃값은 n을 가지게 된다.
이제 반복문을 통해 콜라의 개수에 대해 도출해 내야 하는데 나 같은 경우
애초에 이 문제에서 for 문을 사용하는 것 자체가 아닌듯해 while 문으로 무한 반복 시킨 후
임계점을 넘을 때 정지하도록 했다.
while(true){
answer += (empty / a) * b;
empty = (empty % a) + (empty / a) * b;
if(empty < a){
break;
}
}다음 식의 경우 answer는 순수하게 가진 콜라의 수를 더하게 되며
empty는 answer에 더해진 콜라의 수를 계산해 다음 연산에서 다시 콜라의 수를 더할 수 있게 한다.
여기서 answer는 초깃값 n을 가진 empty로 부터 공병을 콜라로 바꾼 값.
empty는 콜라로 바꾼 answer 값과 함께 갯수 부족으로 인해 바꾸지 못한 공병을 합쳐주는 역할을 하게 된다.
예를 들어 3개의 공병을 주면 1 병의 콜라를 주는데 지금 가진 공병의 수가 25병이라고 하면
공병 24개로 콜라 8병을 바꾸고 1병의 공병이 남을 수밖에 없게 된다.
그런데 남은 1개의 공병을 무시하고 empty를 바꾼 공병 8개로만 계산하게 된다면
오류가 생긴다.
남은 공병 1개와 바꾼 콜라 8 병을 합치면 총 9개의 공병이 생기고 3개를 바꿀 수 있는데
8개로만 계산할 경우 콜라를 2병 밖에 바꾸지 못하므로 정답과 편차가 생기는 것이다.
그렇기 때문에 개수 부족으로 바꾸지 못한 공병의 개수인 (empty % a) 와 정상적으로
바꾼 콜라의 개수 (empty / a) * b를 더해 새로운 empty의 값을 도출하여 다음 연산이
정상적으로 진행될 수 있도록 하는 것이다.
예시 1번의 경우 a = 2 , b = 1, n = 20 의 값을 초깃값으로 준다.
그렇다면 최초 계산은
answer += (20 / 2) * 1 = 10
empty = (20 % a) + (20 / a) * 1 = 10 (0 + 10)
그 다음 계산은
answer += (10 / 2) * 1 = 5 (10 + 5 = 15)
empty = (10 % 2) + (10 / 2) * 1 = 5 (0 + 5)
그 다음 계산은
answer += (5 / 2) * 1 = 2 (10 + 5 + 2 = 17)
empty = (5 % 2) + (5 / 2) * 1 = 3 (1 + 2)
그 다음 계산은
answer = (3 / 2) * 1 = 1 (10 + 5 + 2 + 1 = 18)
empty = (3 % 2) + (3 / 2) * 1 = 2 (1 + 1)
그리고 최종적으로
answer = (2 / 2) * 1 = 1 (10 + 5 + 2 + 1 + 1 = 19)
empty = (2 % 2) + (2 / 2) * 1 = 1 (0 + 1)
로 공병은 1병만 남게 되고 콜라와 교환하기 위한 최소 개수는 2기 때문에
if(empty < a){
break;
}다음의 break 문에 의해 연산을 멈추게 된다.
이제 answer 제출하면 끝임.
간단해 보이지만 그냥 보다보면 뇌가 꼬이는 문제다.
"콜라 그만 쳐먹어 상빈아 이빨 썩어"
그럼 좋은 하루 보내시길. ^오^