[F-Lab 페이백 모각코 50일차] 프로그래머스 콜라 문제 (Java)

학습목표

• 콜라 문제 - 프로그래머스 - 자바

TIL

• 콜라 문제 - 프로그래머스 - 자바

 

 

문제 설명

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

정답은 아무에게도 말하지 마세요.

콜라 빈 병 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

입출력 예 설명

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

 

이전 코테 문제와 더불어 GTP에 문제를 입력하고 접근방법과 핵심을 물어보았다.

 

 

이 문제는 주어진 병의 수를 활용해서 최대한 많은 콜라를 얻는 방법을 찾는 문제입니다. 이를 위해서는 다음과 같은 두 가지 접근 방법을 생각해볼 수 있습니다.

1. **재귀적 접근법**: 문제를 더 작은 하위 문제로 분해해서 푸는 방법입니다. 상빈이가 처음에 가지고 있는 빈 병의 개수에서 시작해서 콜라를 마시고 병을 반환하는 과정을 반복하는 방식으로 문제를 풀 수 있습니다. 이 때, 각 단계에서 받은 콜라의 병 수를 더하고, 새로 얻은 빈 병의 수를 다시 입력으로 사용해서 문제를 재귀적으로 풀 수 있습니다. 그러나 이 접근법은 반복횟수가 많아질 경우 시간복잡도가 커질 수 있습니다.

2. **반복문을 사용한 접근법**: 문제를 풀기 위해서는 주어진 병의 개수를 활용해서 최대한 많은 콜라를 얻는 방법을 찾아야 합니다. 이를 위해서는 먼저 상빈이가 가지고 있는 병의 개수를 a로 나누어 콜라의 개수를 구하고, 이를 반복하는 방식으로 문제를 풀 수 있습니다. 이 때, 남은 병의 개수와 새로 얻은 병의 개수를 더해서 다음 반복의 입력으로 사용하면 됩니다. 이 접근법은 문제를 효율적으로 풀 수 있습니다.

이 문제의 경우 반복문을 사용하는 방법이 더 효율적일 수 있습니다. 그 이유는 병의 개수가 매우 클 경우에도 문제를 빠르게 해결할 수 있기 때문입니다. 그러나 재귀적 접근법도 이해하는데 도움이 될 수 있으므로 두 가지 방법 모두 고려해 보는 것이 좋습니다.

 

말씀하신 대로 반복문을 사용하여 이 문제를 해결하는 Java 코드를 작성해봤습니다. 아래의 코드를 참고하시면 될 것 같습니다.

public class Main {
    public static void main(String[] args) {
        System.out.println(solution(2, 1, 20));  // 기존 문제를 테스트
    }

    public static int solution(int a, int b, int n) {
        int total = 0;
        while (n >= a) {
            int exchange = n / a;  // 교환 가능한 콜라의 개수
            total += exchange * b;  // 받은 콜라를 총 콜라의 개수에 추가
            n = n % a + exchange * b;  // 새로 얻은 빈 병의 수를 계산
        }
        return total;
    }
}

 

이 코드는 `a`를 사용하여 `n`을 나눠서 교환할 수 있는 콜라의 개수를 계산하고, 이를 `total`에 더합니다. 그런 다음, `n`을 업데이트하여 새로 얻은 빈 병의 개수를 반영합니다. 이 과정을 `n`이 `a` 미만이 될 때까지 반복합니다.

주의해야 할 점은, 마지막에 `n`을 업데이트할 때 `exchange * b`를 더해주는 이유는 마시면서 새롭게 얻은 빈 병의 개수를 추가하기 위함입니다. 이는 콜라를 마신 후에도 병을 재사용할 수 있기 때문입니다.

 

문제 이해는

 

일단 반복되는 부분을 코드화 해서 그걸 while문으로 하는 것이다.

while문 조건은 n >= a

 

 

교환 가능한 콜라의 갯수 구하고

받은 콜라를 총 콜라의 개수에 추가

새로 얻은 빈 병의 수를 계산

a,b,n 즉 수식에서는 교환 가능한 콜라의 개수를 구하면

남은 수식은 딱히 어렵지 않아서 다른 문제들 보다 더 쉬운 것 같았다.ㅎ

 

 

 

이 문제는 그리디 문제라고 한다.

그리디 문제가 먼지 항상 궁금하였는데

이 문제가 그리디 문제여서 알게 모르게 쓰이고 많이 어렵지는 않는 다는 것을 알게 되었다.