[알고리즘] 콜라 문제: 수학적으로 닫힌 공식으로 환원하기

상빈이.jpg

문제 본문

오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다.
정답은 아무에게도 말하지 마세요.콜라 빈 병 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 범위를 넘지 않게 주어집니다.

나의 풀이

3줄 접근

1회 시행 이후 남은 병 개수의 합 = m = n - a + b
굳이 a씩 뺄 필요가 없다(예: a = 2, n = 20, b = 1인 경우, 1회 시행 시 20 - 2*10 + 10 = 10개.
10 = n / a (단, 0보다 커야 한다. 예를 들어 n = 2, a = 3인 경우 실행 불가), 10 = b * (n / a)
위와 같이 1회 시행하고 나면 n = n - a + b, n이 a보다 작으면 종료

실제 코드

class Solution {
    public int solution(int a, int b, int n) {
        int totalBottles = 0;
        int quotient;
        while(n / a > 0) {
            quotient = n / a;
            totalBottles += b * quotient;
            n = n - quotient * (a-b);
        }
        
        return totalBottles;
    }
}

분석

• 시간 복잡도: O(logN)
• 공간 복잡도: O(1)
• 사용하는 자료구조: 없음 

장점

• 주석으로 핵심 수식 도출 과정(n = n - quotient * (a-b))을 명확히 설명. 사고 과정이 잘 드러남
• quotient를 뽑아 한 번에 여러 교환을 처리하는 최적화가 적용됨

한계

• n / a > 0은 n >= a와 동일한 조건. 후자가 의도를 더 명확하게 표현함

---

모범답안

class Solution {
    public int solution(int a, int b, int n) {
        return (n > b ? n - b : 0) / (a - b) * b;
    }
}

 

분석

• 시간 복잡도: O(1)
• 공간 복잡도: O(1)
• 사용하는 자료구조: 없음 

장점

• 수학적 공식으로 완전히 환원. 핵심 인사이트는 다음과 같음:
  • 교환 1회당 병이 (a-b)개씩 순감소
  • 따라서 총 교환 횟수 = (n - b) / (a - b) (정수 나눗셈)
  • 총 획득 = 교환 횟수 × b
  • n ≤ b면 교환 불가 → 0 반환

한계

• 공식만 있고 도출 과정이 없어, 코드만 보면 의도 파악이 어려움. 면접에서 "왜 이 공식인가요?" 질문이 반드시 나올 것

최종 개선 코드

class Solution {
    public int solution(int a, int b, int n) {
        int answer = 0;

        while (n >= a) {
            answer += b * (n / a);
            n = b * (n / a) + n % a;
        }

        return answer;
    }
}

무엇이 개선되었나

• n = b * (n / a) + n % a — 교환 후 남은 병을 "새로 받은 병 + 교환 못한 나머지" 로 표현. 내 풀이와 수학적으로 동일하지만 더 직관적

---

인사이트

시뮬레이션으로 맞게 풀었다면,
수학적으로 닫힌 공식으로 환원할 수 있는지를 고민하는 습관을 들여보도록 하자.

Github 링크 (많은 방문 바랍니다)

https://github.com/ginsengcandy/Coding-Test-Practice/commit/d31fe8c4ee2f5708eb094506b228547d7bc09b58

[level 1] Title: 콜라 문제, Time: 0.07 ms, Memory: 84.3 MB -BaekjoonHub · ginsengcandy/Coding-Test-Practice@d31fe8c

문제 출처

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

프로그래머스