문제
길이가 N인 배열 A가 있다.
이 배열은 1, 2, 3 세 값으로만 이루어져 있다.
우리는 이 배열에서 다음 조건을 만족하는 세 인덱스의 순서쌍 (i, j, k)들을 최대한 많이 찾으려고 한다.
배열의 세 인덱스 i, j, k (0 <= i < j < k < N)에 대해서
A[i]=1, A[j]=2, A[k]=3이거나, A[i]=3, A[j]=2, A[k]=1이어야 한다.
단, 한 인덱스는 최대 한 개의 순서쌍에만 들어갈 수 있다.
예를 들어 A = {1, 2, 3, 2, 3, 1}이 주어졌다고 하자.
조건을 만족하는 답은 (0, 1, 4), (2, 3, 5) 가 된다.
(A[0]=1, A[1]=2, A[4]=3 이고 A[2]=3, A[3]=2, A[5]=1)
A가 주어졌을 때, 조건을 만족하는 순서쌍을 최대한 많이 찾아서 보고하는 프로그램을 작성하라.
입력
첫 줄에 N이 주어진다. (1 <= N <= 15,000)
두 번째 줄에 배열 A의 원소들이 공백을 사이에 두고 주어진다.
<서브태스크>
#1 (10점) : N <= 18
#2 (20점) : N <= 100
#3 (35점) : N <= 3000
#4 (35점) : 추가적인 제한 조건 없음
출력
첫 줄에 조건을 만족하는 순서쌍의 최대 개수를 출력하라.
이후 실제 가능한 순서쌍들을 한 줄에 하나씩 출력하라.
가능한 답이 여러 개라면 아무 것이나 출력해도 좋다.
예제
6
1 2 3 2 3 1
2
0 1 4
2 3 5
출처
2020 IOI 한국국가대표선발고사 day2
로그인해야 코드를 작성할 수 있어요.