https://www.acmicpc.net/problem/24502
문제요약
- 숫자들이 있음(N = 10^6, 각각은 10^9)
- 각각을 K의 배수로 만들어야함
- 한번에 한칸씩 1을 이동 가능 : +1 -1
- 최소 회수 구하기
접근법
- 어려웠음. 공식 해설이 나오면 봐야겠음
- 접근하기 전에 이런 생각은 했음
- 주거나 받거나 횟수는 동일 하겠구나
- 주거나 받거나 중에 유리한 쪽이 있겠구나
- 일단 전체 합이 k 배수인지 확인
- 앞에서부터 k 배수를 만들어나가야하는데 할 수 있는 일은
- k로 나눈 나머지가 r
- 뒤로 숫자를 주거나 : r
- 뒤에서 숫자를 받거나 : k - r
- 주면 뒤에 숫자는 a + r, 횟수는 +r
- 받으면 뒤에 숫자는 a - (k - r), 횟수는 +(k - r)
- 그런데 받는 경우 뒤에 숫자가 음수가 되는 경우가 발생할 수 있다
- 음수이면 뒤로 주지는 못함. 받기만 해야함
- -a 였다고 하면, 뒤에 숫자는 b - a, 횟수는 +a
- 뒤에 숫자가 0이 되는 경우가 있다
- 이 경우에는 그 숫자에 대해서는 더 이상 주거나 받는 것은 불필요
- 이를 수식으로 계산해보면 음수인 경우 뒤로 주지 못하는 경우때문에 경우의 수가 1개 또는 2개로 제한되는 것을 확인할 수 있다.
- 즉 앞에서부터 계산을 이어나가면 경우의 수가 제한적임
- 다음 숫자가 0이거나
- 다음 숫자가 양수 1개, 음수 1개
- 이를 이용해서 해결은 하였음
다른 사람 풀이 참고
- 모든 숫자들은 k 나머지 연산
- 숫자들을 계속 누적해나감
- 누적한 숫자를 r이라고 할때
- 주는 것(r), 받는 것(k - r)을 계산해서 작은 쪽을 횟수로 가져감
- 어떻게 누적 합만 가지고서 주고/받고를 판단할 수 있는지??
newbieski