백준 18859 부모님께 큰절 하고

문제

https://www.acmicpc.net/problem/18859

18859번: 부모님께 큰절 하고

 

풀이

1. 입력받은 A를 정렬해본다.

수열이 감소했다가 증가해야하므로 A의 최소값 A[0]는 일종의 기준값이 된다.

2. A[1] - A[0] 공차를 가지는 수열은 존재할 수 밖에 없다.

감소하는 파트는 증가하는 파트든 A[1]은 A[0]옆에 있을 수 밖에 없다.

3. 따라서 A[1] - A[0]를 공차로 가지는 수열을 일단 만들어준다.

이를 담기위한 arr1, 해당 수열에 포함안되는 값을 담기위한 arr2를 만들어준다.

A[0]는 기준값이므로 arr1,arr2에 넣어준다.

이제 배열을 인덱스1부터 순회하자.

지금넣을원소 - arr1의 마지막원소 == A[1] - A[0]라면 arr1에 넣고, 아니라면 arr2에 넣는다.

4. arr2도 등차수열이라면 행복하겠지만, 아닐수도 있다.

그렇다고해서 arr2가 등차수열이 아니라면 정답이 무조건 No는 아니다.

(지식의 부재로 어떤 테스트 케이스인지 콕 집을 수 없으나 직관적으로 알 수 있다. A에 같은 수가 들어가 있다거나 하는..)

5. arr1을 등차수열로 유지한 채 arr1의 원소를 arr2에 넣어서 등차수열로 만들수도 있다.

6. 그 전에 arr2의 인접한 두 원소의 차이를 생각해보자. 그 차이의 종류는 여러개일 것이다. (등차수열이라면 Yes를 출력하고 종료했을 것이므로)

그 중 하나의 차이가 k라하고 하자. arr1에서 마음대로 원소를 넣아서 어찌어찌 등차수열을 만들었다고 하면, 가능한 공차는 k의 약수(1과k를 포함해서)들 중 하나가 될 수 밖에 없다.

모든 종류의 차이에 대해 이를 만족해야한다.(차이의 약수들 중 하나)

따라서 모든 차이의 GCD를 구해준다. 그 GCD의 약수가 arr2의  공차중 하나일 것이다.(만들 수 있다면)

7. GCD의 모든 약수 f에 대해 다음을 시행한다.

7-1. 초항이 기준값이고 공차는 f인 수열을 만들어야한다.

7-2. 우선 그 수열에 대해 arr2에 없는 값을 알아내보자. max(arr2)보다 큰 값은 필요없다.

7-3 arr2에 없는 값은 arr1에서 뺴줘야한다. 만약 없는 값들의 수가 arr1의 원소개수보다 많아진다면 false를 리턴한다.

7-4 arr2에 없는 값에 대해 arr1에 없는 값이 있다면 false를 리턴해준다.

7-5 arr2에 없는 값을 arr1에서 다 빼준 뒤, arr1이 등차수열을 이루지 않는다면 false를 리턴해준다. 

7-6 살아남았다면 true를 리턴해준다. Yes를 출력하고 종료