[백준] 19939번 박 터뜨리기 파이썬 정답 코드

19939번: 박 터뜨리기

---

1. 문제 내용

 

 

2. 접근 방식

• 나눠 담을 수 없는 경우는 언제인가?

문제를 쪼개서 접근하고자 먼저 답을 도출할 수 없는 상황을 고민하였다. 예를 들어 k = 3이라면, 공은 최소 3 + 2 + 1 = 6개는 있어야 한다. 따라서 k + (k - 1) + (k - 2) + ... + 1보다 n이 작을 때는 정답을 구할 수 없다.

 

• 답을 구할 수 있을 때는, 규칙이 무엇인가?
  • n = 10, k = 4 ▶ 1, 2, 3, 4 (3)
  • n = 11, k = 4 ▶ 1, 2, 3, 5 (4)
  • n = 12, k = 4 ▶ 1, 2, 4, 5 (4)
  • n = 13, k = 4 ▶ 1, 3, 4, 5 (4)
  • n = 14, k = 4 ▶ 2, 3, 4, 5 (3)
  • n = 15, k = 4 ▶ 2, 3, 4, 6 (4)
  • n = 16, k = 4 ▶ 2, 3, 5, 6 (4)
  • n = 17, k = 4 ▶ 2, 4, 5, 6 (4)
  • n = 18, k = 4 ▶ 3, 4, 5, 6 (3)

규칙을 찾아내고자 k를 고정한 채 n 값을 하나씩 증가시켜보았다. 각각의 박이 1, 2, 3, 4개의 공을 나눠 가지며, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 (3)이라는 의미이다.

규칙은 간단하다. k + (k - 1) + (k - 2) + ... + 1의 값이 kk라고 한다면, 정답이 3일 때는 (n - kk) % k = 0일 때이고, 4일 때는 나머지가 0이 아닐 때이다.

 

 

3. 정답 코드

• 40ms 시간이 걸리는 코드이다.

n, k = map(int, input().split())

# k + (k - 1) + (k - 2) + ... + 1
kk = sum([x for x in range(1, k + 1)]) # same with (k * (k + 1)) // 2

if n < kk:
    print(-1)

elif (n - kk) % k == 0:
    print(k-1)

else:
    print(k)

흥미롭게도, kk를 구할 때 sum을 이용하는 것이 (k * (k + 1)) // 2보다 4ms 더 빠르다. 리스트 comprehension과 sum 함수의 최적화가 무척 잘 되어 있음을 다시 한 번 깨달았다.