BOJ 2787 : 흔한 수열 문제

문제 링크 : https://www.acmicpc.net/problem/2787

 

• 1 x y v - x번째 수부터, y번째 수 중 제일 큰 값은 v
• 2 x y v - x번째 수부터, y번째 수 중 제일 작은 값은 v

이런 식으로 수열에 관한 정보를 주면 이들을 만족하는 수열을 찾아서 출력하면 된다.

수열의 정보에 관한 문제가 대부분 펜윅트리로 풀려서 그쪽으로 생각을 해봤는데 잘 안 됐다.

 

그러다가 N 제한이 200 인 것이 이상해서 생각해봤는데 이분매칭이 떠올랐다.

2 ~ 10 번째 수의 최댓값이 15 라면,

2 ~ 10 번째의 각 칸들을 1 ~ 15 와 연결해주고 매칭하면 된다.

 

하지만, 이 방법은 문제가 있다.

매칭은 정상적으로 되지만, 2 ~ 10 번째 수의 최댓값이 15 면 15가 무조건 존재한다는 소리다.

이분 매칭은 이를 보장해줄 수 없다.

 

발상의 전환을 하면 된다.

각 칸에 존재할 수 있는 수들을 연결하는 것이 아닌, 존재할 수 없는 수들을 파악하고 이분매칭을 하면 된다.

2 ~ 10 번째 수의 최댓값이 15라는 정보가 주어지면,,

1번째 칸과 11 ~ N 번째 칸은 15가 절대로 될 수 없다.

또한 2 ~ 10 번째 칸은 16 ~ N 이 절대로 될 수 없다.

이런 식으로 연결될 수 없는 관계를 파악하고 이분매칭을 하면 정확한 수열을 얻을 수 있다.