콜라 문제

📍 콜라 문제

💡 문제

빈 병 a개를 가져다주면 콜라 b병을 주는 마트가 있을 때, 빈 병 n개를 가져다주면 몇 병을 받을 수 있는지 계산하는 문제입니다. 보유 중인 빈 병이 a개 미만이면, 추가적으로 빈 병을 받을 순 없습니다.

⚠️ 제한사항

1 ≤ b < a ≤ n ≤ 1,000,000
정답은 항상 int 범위를 넘지 않게 주어집니다.

✅ 풀이

☝️ 첫 번째 풀이

몫과 나머지를 더한 값이 a보다 작아질 때까지 n을 a로 계속 나눈다. 이때, 몫에는 b를 곱해 합하고 나머지는 다음 몫에 더하는 연산을 반복해줬다.

class Solution {
  fun solution(a: Int, b: Int, n: Int): Int {
  	// 이 과정도 반복문 내부에 작성할 수 있지 않을까?
    var (div, mod) = Pair(n/a * b, n%a)
    // 처음 몫을 대입해주는 점이 마음에 들지 않았다.
    var answer: Int = div
 
    while ((div + mod) >= a) {
      var notUsed = div + mod
      // 여기도 더 줄일 수 있을 것 같다.
      div = notUsed/a * b
      mod = notUsed%a
      answer += div
    }
 
    return answer
  }
}

✌️ 두 번째 풀이

첫 번째 풀이에서 아쉬웠던 점을 반영해 다시 풀어보았다.

class Solution {
  fun solution(a: Int, b: Int, n: Int): Int {
    var answer: Int = 0
    // n을 변수에 저장
    var bottles = n
 
    while (bottles >= a) {
      answer += bottles/a * b
      bottles = bottles/a*b + bottles%a
    }
 
    return answer
  }
}

🔥 다른 사람의 풀이

다른 사람의 풀이 중 신기한 게 있었다. 도대체 어떻게 푼 것일까.

class Solution {
  fun solution(a: Int, b: Int, n: Int): Int {
    return (n - b) / (a - b) * b
  }
}

원리는 정말 간단했다. 각 교환마다 새로운 병을 받지 않았을 때의 최대 교환 횟수에 새로 받는 병(b)를 곱해주는 방식이었다.

최대 교환 횟수는 어떻게 구할까?

빈 병의 수(n)를 교환할 때 필요한 병의 수(a)로 나눠주면 된다. 이 과정을 새로 받는 병(b)이 없다고 가정하고 계산하면 된다. 내가 이해한 건 다음과 같다.

한 번의 교환으로 a - b 만큼의 병이 없어진다.
- 따라서, 한 번의 교환에 필요한 병의 수는 a - b이다.
조건에 따르면, a는 항상 b보다 크다. 따라서 마지막 교환에는 b를 받지 못한다.
- 이 경우를 고려해 교환 가능한 빈 병의 수를 조정해야 한다.
- 마지막 교환에는 a 만큼의 병이 없어지고, a 보다 작은 수 만큼이 남게된다.
- a 보다 작은 수는 a - 1이나 a - 2도 가능하지만, a - b로 생각할 수도 있다.
- 이를 식으로 나타내면, n - a + (a - b)가 되고, n - b로 줄일 수 있다.
교환할 수 있는 빈 병의 수를 한 번의 교환으로 소모되는 병의 수로 나눠주면 최대 교환 횟수를 구할 수 있다.

위와 같은 방식을 사용하면, (n - b) / (a - b) * b 로도 문제를 풀 수 있다.

💭 후기

세상은 넓고 똑똑한 사람은 많다. 수학을 소홀히 하면 안되겠다는 생각이 들었다. 사실 이전부터 하고는 있었지만.. 하루이틀 해서 느는 게 아닌걸..