https://www.acmicpc.net/problem/1829
문제요약
- k, k + 1, k + 2, ... 숫자가 있음(10만개, k는 50만까지 가능)
- 임의의 위치를 지정해서 동일한 값을 뺄 수 있음 => 이것을 1회로 봄
- 가능한 적은 횟수로 모든 숫자를 0으로 만들기
- 엄청 어려웠는데 티어상태가??
접근법 : 숫자 종류 줄이기 - 잘 안됨
- 숫자가 n가지 있으므로, 잘 줄이면 n/2, n/4, ... 로 줄지 않을까
- 10 11 12 13 14 .... => 9 11 11 13 13.. => 7 11 11 11 11 ...
- 맞는 듯 보였으나 여러가지 예외가 생기고, 처리가 곤란해짐
접근법 : 비트로 줄이기 - 부족함
- 숫자를 이루는 비트가 있을 것임
- n개의 숫자를 구성하는 비트를 파악함
- 1, 2, 4, ... 의 비트를 갖고 있는 숫자들에서 값을 빼줌
- 빼주다보면 한번에 빼줄 수 있는 것들이 있고, 그것들도 같이 처리를 해줌 : 모든 숫자가 공통으로 갖고 있는 비트들이 있음
- 숫자가 1, 2, 3, ...이면 잘 먹히는데 예외가 있음
- 100 101 102 103 => 3번만에 됨
- 100 101 102 103 104 105 106 107 => 5번만에 됨
- 4번만에 되어야함. 왜냐면
- 100 101 102 103 100 101 102 103 ==> 100 101 102 103과 동일한 횟수
접근법 : 비트 줄이기 + 접기 - 됨
- 비트로 줄이기에서 마지막에 잘 안되는 경우를 따져보게됨
- 숫자들 A가 있고, 동일한 숫자들 A'가 있는 수열 즉 A A' 이면
- 결국 A를 처리하는데 드는 횟수와 동일 할 것임
- 이를 응용하면 K, K + 1, ...... K + x, K + x + 1 구조에서 뒷부분에서 x를 빼주면 왼쪽 오른쪽 구조가 같아짐
- 이때 구조가 되게 처리해야 쓸데없는 처리가 줄면서 횟수가 최적화됨
- 그런데 3 4 5 6 7 과 같은 구조에서도 그렇게 처리를 해야할까?
- 3 4 5 6, 3 ==> 1회
- 3 4, 3 4, 3 ==> 2회
- 3, 3, 3, 3, 3 => 3회
- 0 0 0 0 0 => 4회
- 비트줄이기를 사용하면
- 2 4 4 6 6 => 1회, 1을 빼줌
- 0 4 4 4 4 => 2회, 2를 빼줌
- 0 0 0 0 0 => 3회, 3을 빼줌
- 결국 비트로 줄일때와 접기를 했을때 횟수를 비교하게 됨
- 비트 줄이기가 적으면 비트를 줄이고
- 안되면 접어서 처리함
- 정답 출력을 위한 자료구조로 배열 + 배열에 연관된 위치들 + 접는 함수 + 적절한 을 구하는 함수 등등 구현이 많았음
newbieski