[2025.01.22] 콜라 문제

문제 설명

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

정답은 아무에게도 말하지 마세요.
콜라 빈 병 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	빈 병 20개 중 18개를 마트에 가져가서, 6병의 콜라를 받습니다. 이때 상빈이가 가지고 있는 콜라 병의 수는 8(20-18+6=8)개 입니다. 빈 병 8개 중 6개를 마트에 가져가서 2병의 콜라를 받습니다. 이때 상빈이가 가지고 있는 콜라 병의 수는 4(8-6+2=4)개 입니다. 빈 병 4개 중 3개를 마트에 가져가서 1병의 콜라를 받습니다. 이때 상빈이가 가지고 있는 콜라 병의 수는 2(4-3+1=2)개 입니다. 3번의 교환 동안 상빈이는 9(6+2+1=9)병의 콜라를 받았습니다.

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>

using namespace std;

int solution(int a, int b, int n) {
    int answer = 0;
    int remain=0; // 교환하고 난 후 나머지
    int replace=0; // 교환 받은 콜라
    
    // 콜라 교환
    while(n>a-1) // 남은 콜라를 더이상 교환하지 못할 때까지
    {
        replace=n/a; // 교환 받은 콜라 수 구하기
        remain=n%a; // 교환하고 남은 콜라 수 구하기
        n=replace*b+remain; // 현재 가지고 있는 콜라 수 업데이트
        
        answer+=replace*b; // 교환 받은 콜라 수 저장
    }
    return answer;
}

콜라를 교환하는 방법에 대해서 생각해 보았는데 결국 교환 받은 콜라는 n을 a로 나눈 나머지에 b를 곱한 것이다. 하지만 여기서 놓치지 말아야 하는 것이 나머지가 존재한다는 것이다. 만약 내가 5개의 콜라병을 가지고 있느데 2개를 1개로 교환해준다는 상황이라면 2개씩하여 총 4개를 교환하고 하나가 남는다. 이 남은 한 병을 잊지 말고 현재 내가 가진 콜라의 수에 포함시켜야 한다는 것이다. 즉, 현재 내가 가지고 있는 콜라의 수는 교환 받은 콜라에 나머지를 더한 것이어야만 한다.

 

나머지와 교환 받은 콜라를 저장할 변수를 각각 선언하고 초기화 한다. n이 a보다 작아지는 순간 더이상 교환을 받을 수 없기 때문에 그 때까지 계속 콜라를 교환하는 것으로 반복문의 조건을 짠다. 반복문 안에서는 교환 받은 콜라 수와 나머지를 구하고 그것을 이용해 결국 현재 내가 가지고 있는 콜라수를 n으로 업데이트 한다. 마지막으로 교환 받은 콜라의 수를  answer에 누적하여 저장한다.

 

이렇게 모든 교환을 마치면 answer를 반환한다.

 

 

오답 노트

반복문의 조건을 a가 2일 경우만 생각하고 만들어서 n>1로 하였다가 거의 모든 테스트 케이스에서 시간 초과가 나왔다. 시간 초과가 나오는 이유가 궁금하여 Visual Studio를 돌려서 확인해보았는데 반복문이 n값을 계속 2로 찍으면서 돌아가고 있었다. 2가 되면 더이상 교환할 수 없어 나와야 하는데 조건이 1일 때만 나올 수 있게 되어 있으니 계속 2 값을 가지고 돌고 있었다.

#include <string>
#include <vector>

using namespace std;

int solution(int a, int b, int n) {
    int answer = 0;
    int remain=0;
    int replace=0;
    while(n>1)
    {
        replace=n/a;
        remain=n%a;
        n=replace*b+remain;
        
        answer+=replace*b;
    }
    return answer;
}

 

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/132267

프로그래머스