프로그래머스 [연습문제 / 콜라 문제](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 132267 콜라 문제

---

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/132267

문제 설명:

빈 병 a개를 가져다주면 콜라 b병을 주는 마트에서, 처음 가지고 있는 빈 병 n개로 총 몇 병의 콜라를 받을 수 있는지 계산하는 문제입니다. 교환 후 받은 콜라를 마시면 다시 빈 병이 되므로, 빈 병이 a개 미만이 될 때까지 반복적으로 교환할 수 있습니다. 반복문과 나눗셈 연산을 활용한 시뮬레이션 문제입니다.

---

문제 해결 코드

#include <string>
#include <vector>
using namespace std;

int solution(int a, int b, int n) {
    int answer = 0;
    
    // 빈 병이 a개 이상일 때까지 반복
    while(n >= a) {
        int receivedCola = (n / a) * b;  // 교환으로 받은 콜라 병 수
        int remainBottles = n % a;        // 교환하고 남은 빈 병 수
        
        answer += receivedCola;           // 받은 콜라를 총합에 누적
        n = remainBottles + receivedCola; // 남은 병 + 새로 받은 콜라(마시면 빈 병이 됨)
    }
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 시뮬레이션 방식으로 교환 과정을 반복합니다. 현재 가진 빈 병을 a로 나눈 몫만큼 교환 횟수를 구하고, 각 교환에서 b병씩 받습니다. 교환 후 남은 빈 병과 새로 받은 콜라(마시면 빈 병)를 합쳐서 다음 교환에 사용합니다. 이 과정을 빈 병이 a개 미만이 될 때까지 반복합니다.
• 구현 세부사항:
  • n / a로 교환 가능한 횟수를 계산하고, 여기에 b를 곱해 받을 콜라 수를 구합니다.
  • n % a로 교환하고 남은 빈 병 수를 계산합니다.
  • 받은 콜라를 answer에 누적하여 총 콜라 수를 추적합니다.
  • 남은 빈 병과 새로 받은 콜라(마시면 빈 병)를 더해 다음 반복의 n 값으로 갱신합니다.
  • n이 a보다 작아지면 더 이상 교환할 수 없으므로 반복을 종료합니다.
• 시간/공간 복잡도: 시간 복잡도는 O(log n)입니다. 매 반복마다 n이 대략 n / a 수준으로 줄어들기 때문에 로그 시간에 수렴합니다. 공간 복잡도는 O(1)로, 몇 개의 변수만 사용하여 추가 메모리가 거의 필요하지 않습니다.

---

실행 예시

테스트 케이스 1:

입력: a = 2, b = 1, n = 20

실행 과정:

• 1회차: 20 / 2 = 10회 교환 → 10병 받음, 남은 병: 0 + 10 = 10병
• 2회차: 10 / 2 = 5회 교환 → 5병 받음, 남은 병: 0 + 5 = 5병
• 3회차: 5 / 2 = 2회 교환 → 2병 받음, 남은 병: 1 + 2 = 3병
• 4회차: 3 / 2 = 1회 교환 → 1병 받음, 남은 병: 1 + 1 = 2병
• 5회차: 2 / 2 = 1회 교환 → 1병 받음, 남은 병: 0 + 1 = 1병
• 종료: 1병은 교환 불가

출력: 10 + 5 + 2 + 1 + 1 = 19병

테스트 케이스 2:

입력: a = 3, b = 2, n = 20

실행 과정:

• 1회차: 20 / 3 = 6회 교환 → 12병 받음, 남은 병: 2 + 12 = 14병
• 2회차: 14 / 3 = 4회 교환 → 8병 받음, 남은 병: 2 + 8 = 10병
• 3회차: 10 / 3 = 3회 교환 → 6병 받음, 남은 병: 1 + 6 = 7병
• 4회차: 7 / 3 = 2회 교환 → 4병 받음, 남은 병: 1 + 4 = 5병
• 5회차: 5 / 3 = 1회 교환 → 2병 받음, 남은 병: 2 + 2 = 4병
• 6회차: 4 / 3 = 1회 교환 → 2병 받음, 남은 병: 1 + 2 = 3병
• 7회차: 3 / 3 = 1회 교환 → 2병 받음, 남은 병: 0 + 2 = 2병
• 종료: 2병은 교환 불가

출력: 12 + 8 + 6 + 4 + 2 + 2 + 2 = 36병

---

결과

나눗셈의 몫과 나머지를 활용한 간결한 시뮬레이션으로 문제를 효율적으로 해결했습니다. 매 반복마다 빈 병 수가 급격히 감소하므로 O(log n) 시간에 빠르게 답을 구할 수 있습니다. 수학적 접근으로 수식을 단순화하여 O(1)에 해결할 수도 있지만, 시뮬레이션 방식이 더 직관적이고 이해하기 쉽습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!