[문제풀이 후기] 프로그래머스 #132267 - 콜라 문제

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

 

기본 상위 코드

const [a, b, n] = [2, 1, 20];

// 총 받은 병 개수, 남은 병 개수
let [result, remain] = [0, n];

 

첫 번째 시도 (결과 : 실패)

 

접근 방식

1. 교환 가능한 병의 개수가 남아있을 때까지 반복
2. 지급받는 의 개수 = 남은 병 개수 / 교환에 필요한 병 개수
3. 남은 병 개수 = 교환에 사용하지 않은 병 개수 + 지급받은 병 개수

while (remain >= a) {
  const count = Math.floor(remain / a);

  result += count;
  remain = (remain % a) + count * b;
}

return result;

 

실패 원인 : 지급받는 병의 단위를 1개로 계산함

---

두 번째 시도 (결과 : 성공)

while (remain >= a) {
  const count = Math.floor(remain / a) * b;

  result += count;
  remain = (remain % a) + count;
}

return result;

---

규칙

# 남은 병의 개수
a 개를 내면 b 개를 받는다.
-> 1번 교환할 때마다 남은 병의 개수는 (a - b) 개씩 줄어든다.

# 남은 병의 최소 개수
아무리 교환해도 최소 b 개는 남는다.

# 더 이상 교환이 불가할 때까지 반복 = 최대 교환 가능 횟수 (k 번)
n - (a - b) - (a - b) - ... >= b
-> n - k(a - b) >= b
-> n - b >= k(a - b)
-> (n - b) / (a - b) >= k
-> k = Math.floor((n - b) / (a - b))

# 결론
총 획득하는 병의 개수 = 최대 교환 가능 횟수 * b
=> Math.floor((n - b) / (a - b)) * b

 

세 번째 시도 (결과 : 성공)

return Math.floor((n - b) / (a - b)) * b;

 

효과

시간 : 0.44 ms -> 0.04 ms

 

후기

도대체 저 규칙을 처음에 생각해 낸 사람은 누굴까...
얼마나 해야 저 경지에 오를 수 있을까...