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

콜라 문제

문제 링크

콜라 문제

분석

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

마트에 주어야 하는 병 수는 a, a개를 가져다 주면 마트가 주는 콜라 병 수는 b, 가지고있는 콜라 병 수는 n입니다.

현재 가지고 있는 빈 병 중 콜라를 몇 개 교환 받을 수 있는지 구합니다.
식은 $(n \div a) \times b$입니다.

교환 받을 수 있는 개수와 개수가 부족해 교환받지 못한 낱병의 합을 구해 나중에 다시 교환 받습니다.
식은 $((n \div a) \times b) + (n \bmod a)$입니다.

이 과정을 더이상 교환 받을 수 없을 때까지 반복합니다.

풀이

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)