https://www.acmicpc.net/problem/31927
문제요약
- N의 숫자가 주어짐(1 ~ 5000)
- 두 개의 숫자를 골라서 한쪽은 +x, 한쪽은 -x를 할 수 있음(0 < x <= 1000000)
- N/2 번 이하로 연산했을때 내림 차순 정렬이 가능한지 판단(단조 감소)
접근법
- 양쪽 끝이 엄청 크고 엄청 작으면 유리함
- 그 다음 끝도 엄청 크고 엄청 작으면 유리함
- 주어진 숫자가 1 ~ 5000이라서 x가 적당히 크면 숫자를 잘 구성할 수 있을 것 같음
- 일단 1, N은 x=1000000을 이용해서 연산을 함
- 2, N - 1은 조건을 만족하는 가장 큰 x를 찾아서 연산을 함
- x가 꼭 1000000이 아닐 수 있음(양쪽 숫자가 무엇인가에 따라서)
- 예를 들어 1,2,1,5000 인 경우에
- 첫번째 연산이 끝나고 1000000+1, 2, 1, 5000-1000000
- 두번째 연산에서는 한쪽에 +1000000 - 1이 가능하지만 다른 쪽은 1 - (1000000-1)을 해버리면 값을 넘어서서 안됨(5000-1000000 보다는 작아야함)
- 이런식으로 적절한 x를 찾다가보면 원하는 순서를 만들 수 있음
- x가 0인 경우에는 패스
newbieski