[프로그래머스][C++] 콜라 문제

콜라 문제

문제 링크

콜라 문제

제한사항

• 1 ≤ b < a ≤ n ≤ 1,000,000
• 정답은 항상 int 범위를 넘지 않게 주어집니다.

입출력 예

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

입출력 예 #1
본문에서 설명한 예시입니다.

입출력 예 #2
빈 병 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)병의 콜라를 받았습니다.

분석

일반적으로 있는 콜라 문제입니다.

현재 가지고 있는 빈 병 중 콜라를 몇 개 교환 받을 수 있는지 구합니다.
교환 받을 수 있는 개수와 개수가 부족해 교환받지 못한 낱병의 합을 구해 나중에 다시 교환 받습니다.
이 과정을 더이상 교환 받을 수 없을 때까지 반복합니다.

풀이

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

반복문은 교환을 받을 수 있는 빈 병이 마트에 주어야 하는 개수보다 적어져 교환 받을 수 없을 때까지입니다.

n / a * b로 교환을 통해 받은 콜라의 개수를 구합니다.

n % a로 교환하지 못한 낱병의 개수를 구합니다.
낱병의 개수에 교환 받은 콜라의 개수를 더해 다시 교환 받을 수 있도록 값을 저장합니다.

성능 요약

n이 매번 a로 나눈 몫만큼 줄어드는데, 지수적으로 감소하지는 않지만 로그에 가깝게 줄어듭니다.
그러므로 시간 복잡도는 $O(log \, n)$입니다.

공간 복잡도는 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 4.27MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.16MB)
테스트 4 〉 통과 (0.01ms, 3.68MB)
테스트 5 〉 통과 (0.01ms, 4.13MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 4.14MB)
테스트 8 〉 통과 (0.01ms, 3.63MB)
테스트 9 〉 통과 (0.01ms, 4.2MB)
테스트 10 〉 통과 (0.01ms, 4.21MB)
테스트 11 〉 통과 (0.01ms, 4.21MB)
테스트 12 〉 통과 (0.03ms, 4.2MB)
테스트 13 〉 통과 (0.01ms, 4.2MB)
테스트 14 〉 통과 (0.05ms, 4.21MB)