[Java] 프로그래머스(level-1) - 콜라 문제

자세한 문제 내용은 콜라 문제 링크를 참고하자.

문제 풀이

---

이 문제는 나눗셈과 나머지연산을 잘 활용하면 쉽게 풀 수 있다.
먼저 어떤 패턴으로 답을 요구하는지 알아보자.

문제의 이미지를 보면 20병을 가져가서 10병을, 10병을 가져가서 5병을, 5병을 가져가서 2병을(나머지 1병이 남음), 2병을 가져가서 1병을 가져와 남은 1병과 함께 다시 1병을 받아온다.
잘 보면 빈 병을 가져가서 바꿀 수 있는만큼 나눠진 병만큼 받을 수 있고, 이 때 남은 빈 병과 합쳐 다시 새 콜라병을 받아올 수 있음을 알 수 있다.

아이디어 도출

나눗셈과 나머지연산을 활용하여 빈 병을 가져가서 새 병을 가져오는 식을 도출하였다.

• 빈병을 가져가 새 병을 가져오는 과정 : n = (n/a)*b + (n%a)
  • 문제에선 b를 입력으로 받아 처리하기에 교환할 수 있는 b를 꼭 고려해야 한다.
• 새 병을 가져온 횟수 : (n/a)*b
• 가지고 있는 빈병(n)이 교환에 필요한 빈병(a)보다 작다면 더 이상 교환할 수 없다.

위 식을 적용하면 빈병을 가져가 새병을 가져올 때마다 새 콜라병을 몇번 받았는지 알 수 있다.

a=2, b=1, n=20
n=20 -> (20/2)*1 + (20%2) = 10+0 = 10
    가져온 새 콜라병:10병
n=10 -> (10/2)*1 + (10%2) = 5+0 = 5
    가져온 새 콜라병:5병
n=5 -> (5/2)*1 + (5%2) = 2+1 = 3
    가져온 새 콜라병:2병
n=3 -> (3/2)*1 + (3%2) = 1+1 = 2
    가져온 새 콜라병:1병
n=2 -> (2/2)*1 + (2%2) = 1+0 = 1
    가져온 새 콜라병:1병

총 19병의 새 콜라병을 받을 수 있음. 

여기서 중요한 점은 가지고 있는 빈 병(n)이 교환 가능한 빈병(a)보다 적게 가지고 있으면 더 이상 교환 할 수 없다는 것이다.
결국 n이 a보다 작다면 교환할 수 없으므로 반복문을 탈출하면 된다는 조건을 암시하는 것으로 이해하였다.

이제 위에서 구한 아이디어를 통해 코드를 작성해보자.

// 빈 a병의 콜라병 당 b병의 새 콜라병을 받을 수 있다.
// n = 가지고 있는 빈 콜라병
int answer = 0;

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

로직 자체는 단순하다.

1. while문을 돌며 보유중인 빈병(n)이 교환 할 수 있는 빈병(a)보다 작다면 탈출하면 된다.
   
2. 반복문 내부에서는 n을 새 병으로 교환 후의 빈병과 새 병으로 교환하기 전 남았던 빈병들을 합쳐 가지면서 계속 교환해나간다.
   
3. 이 때, 반복문을 순회하면서 교환한 새 콜라병의 갯수[(n/a)*b] 를 더해나가면 된다.

작성 코드

---

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();
        int n = sc.nextInt();

        long start = System.currentTimeMillis();
        solution(a, b, n);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }
    
    public static int solution(int a, int b, int n) {
        // 빈 a병의 콜라병 당 b병의 새 콜라병을 받을 수 있다.
        // n = 가지고 있는 빈 콜라병
        int answer = 0;

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

        return answer;
    }
}

회고

• 나눗셈과 나머지연산을 잘 조합해서 생각하니 아이디어는 금새 떠올랐다. 하지만 b를 제대로 고려하지 않아 코드를 2번 작성하게 되었다. 문제를 반드시 꼼꼼하게 살펴야 한다.

출처

• 프로그래머스 콜라 문제