https://www.acmicpc.net/problem/2746
문제 설명
- 1 ~ 1,000,000 숫자 50만개가 주어짐
- 정확히 2개를 제거해서 어떤 원소가 이 원소를 제외한 다른 것들의 합이 되는 배열을 만들기
- 2개를 제거하는 경우의 수 구하기
접근법
- 배열에서 가장 큰 값이 이런 조건을 만족시킨다는 것은 알겠음
- 2개를 제거하는 경우
- 가장 큰 값이 있다고 치고, 다른 값들의 합 - 두 개 == 가장 큰 값이 되면 되는데
- 그리고 제거 하는 값 중에서 가장 큰 값이 있는 경우에 로직이 꼬임
- 1개를 제거하는 경우
- 다른 값들의 합 - 1개 == 가장 큰 값이면 되는데
- 제거하는 값 중에서 가장 큰 값이 있는 경우에 로직이 꼬임
- 0개를 제거하는 경우
- 다른값들의 합 == 가장 큰 값이면 됨
- 10, 3 2 3 17 17 1 1 5 6 1 => 2
- 10, 6 4 1 1 1 19 1 19 7 17 => 0
- 5, 2 2 4 4 4
- 5, 2 2 4 4 6
- 여러가지 테스트를 해봤는데 쉽지 않았음
다른 접근법
- lower_bound, upper_bound로 제거할 값, 다른 값 찾는 방식으로 진행했었는데 생각하기 쉽지 않음
newbieski