루미 알고리즘

#1108브론즈먼 카드먼 카드

KOI 2025 1차코딩초등부 1번출제 오주원이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

먼 카드

원제: 먼 카드

문제

자연수가 적힌 카드 2N2N장이 있다. 이 카드들은 일렬로 왼쪽에서 오른쪽으로 나열되어 있다.

각 카드에는 11 이상 NN 이하의 자연수가 정확히 하나씩 적혀 있다. 왼쪽에서 ii(1≤i≤2N1 \le i \le 2N)번째에 놓인 카드에 적힌 자연수를 XiX_i라고 하자.

1≤k≤N1 \le k \le N인 각 kk에 대해, kk가 적힌 카드는 정확히 두 장이다. 즉, 11부터 NN까지의 각 자연수는 정확히 두 장의 카드에 적혀 있다.

정올이는 자연수 kk가 적힌 두 카드 사이에 놓인 카드의 개수를 "kk 사이 카드 수"라고 부르기로 했다.

예를 들어, 아래 그림과 같이 카드가 놓여있다고 생각해 보자. 아래 그림에서 N=4N = 4이고, X1=1X_1 = 1, X2=2X_2 = 2, X3=2X_3 = 2, X4=4X_4 = 4, X5=3X_5 = 3, X6=1X_6 = 1, X7=3X_7 = 3, X8=4X_8 = 4이다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

  • 11이 적힌 두 카드 사이에는 차례로 22, 22, 44, 33이 적힌 카드가 있으므로, "11 사이 카드 수"는 44이다.
  • 22가 적힌 두 카드 사이에는 아무 카드도 없으므로, "22 사이 카드 수"는 00이다.
  • 33이 적힌 두 카드 사이에는 11이 적힌 카드만 있으므로, "33 사이 카드 수"는 11이다.
  • 44가 적힌 두 카드 사이에는 차례로 33, 11, 33이 적힌 카드가 있으므로, "44 사이 카드 수"는 33이다.

위의 사례에서 "kk 사이 카드 수"들 중 가장 큰 것은 "11 사이 카드 수"로, 그 값은 44이다.

정올이는 11부터 NN까지의 모든 자연수 kk에 대한 "kk 사이 카드 수" 중 가장 큰 값을 구하고 싶다.

카드가 나열된 순서대로 카드에 적힌 자연수가 주어질 때, 모든 "kk 사이 카드 수" 중 가장 큰 값을 구하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤2 0001 \le N \le 2\,000
  • 1≤i≤2N1 \le i \le 2N인 각 ii에 대해, 1≤Xi≤N1 \le X_i \le N
  • 1≤k≤N1 \le k \le N인 각 kk에 대해, kk가 적힌 카드는 정확히 두 장이다. 즉, X1X_1, X2X_2, ⋯\cdots, X2NX_{2N} 중에서 kk가 정확히 두 번 나타난다.

부분문제

  1. (10점) N≤2N \le 2
  2. (15점) 답은 00 또는 11이다.
  3. (15점) 답은 2N−32N - 3 또는 2N−22N - 2이다.
  4. (20점) N≤500N \le 500
  5. (40점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 정수 NN이 주어진다.

두 번째 줄에 2N2N개의 정수 X1X_1, X2X_2, ⋯\cdots, X2NX_{2N}이 공백을 사이에 두고 주어진다.

출력 형식

첫 번째 줄에 답을 출력한다.

예제

예제 1

입력
4
1 2 2 4 3 1 3 4
출력
4

예제 2

입력
4
1 2 3 4 4 3 2 1
출력
6

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2025년 1차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.