루미 알고리즘

#1135골드주사위 탑 쌓기주사위 탑 쌓기

KOI 2026 2차코딩초등부 2번, 중등부 1번출제 박상훈이 문제가 어렵다면 — 배우는 순서 보기

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

주사위 탑 쌓기

원제: 주사위 탑 쌓기

문제

상훈이는 NN개의 정육면체 주사위를 가지고 있다. 주사위는 순서대로 11번 주사위, 22번 주사위, ⋯\cdots, NN번 주사위라고 부른다.

모든 주사위의 각 면에는 11 이상 66 이하의 정수가 하나씩 적혀 있다. 하나의 주사위에서 서로 다른 두 면에 적힌 수는 항상 다르며, 서로 마주 보는 두 면에 적힌 수의 합은 항상 77이다.

상훈이는 NN개의 주사위를 사용하여 주사위 탑 쌓기를 하려고 한다. 구체적인 과정은 다음과 같다.

  1. 바닥에 NN개의 주사위를 모두 굴린다.
  2. 각 주사위의 윗면에 적힌 수를 기록한다. 11번 주사위부터 NN번 주사위까지 윗면에 적힌 수를 순서대로 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이라고 한다.
  3. 바닥에 놓인 주사위 중 11개 이상을 선택하여 책상 위에 새로운 탑 하나를 만든다. 주사위를 바닥에서 들어 옮길 수는 있지만, 주사위의 방향을 바꾸어서는 안 된다. 선택한 주사위들을 쌓는 순서는 자유롭게 정할 수 있고, 이 주사위들은 모두 수직으로 일렬로 쌓아야 한다. 이때, 서로 맞닿은 두 면에 적힌 수는 같아야 한다.
  4. 바닥에 남은 주사위가 없을 때까지 과정 3. 을 반복한다.

예를 들어, 주사위 탑 쌓기는 다음과 같이 진행될 수 있다.

  1. 상훈이가 바닥에 44개의 주사위를 굴렸더니, 11번 주사위부터 44번 주사위까지 윗면에 적힌 수가 각각 33, 33, 55, 44였다.
  2. 상훈이는 바닥에서 11번, 22번, 44번 주사위를 선택했다. 그 후, 아래에서부터 11번, 44번, 22번 주사위 순서가 되도록 탑을 쌓았다. 11번 주사위의 윗면과 44번 주사위의 아랫면에는 모두 33이 적혀 있으며, 두 면은 서로 맞닿아 있다. 또한, 44번 주사위의 윗면과 22번 주사위의 아랫면에는 모두 44가 적혀 있으며, 두 면은 서로 맞닿아 있다.
  3. 상훈이는 바닥에 남아 있는 33번 주사위를 선택하여, 주사위 하나로 이루어진 탑을 쌓았다.
  4. 바닥에 남은 주사위가 없으므로 주사위 탑 쌓기를 종료한다. 상훈이는 총 22개의 탑을 만들었다.

상훈이는 탑을 쌓는 방법을 적절히 정하여, 만들어지는 탑의 수를 최소화하려고 한다. NN개의 주사위를 굴린 후 각 주사위의 윗면에 적힌 수가 주어질 때, 만들어지는 탑의 수의 최솟값을 구하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 2≤N≤200 0002 \le N \le 200\,000
  • 정수 ii (1≤i≤N)(1 \le i \le N)에 대하여 1≤Ai≤61 \le A_i \le 6

부분문제

  1. (8점) N=2N = 2
  2. (28점) 주사위의 윗면에 적힌 수는 33 또는 44이다. 즉, 정수 ii (1≤i≤N)(1 \le i \le N)에 대하여 Ai=3A_i = 3 또는 Ai=4A_i = 4이다.
  3. (31점) 임의의 서로 다른 두 정수 xx, yy (1≤x,y≤6)(1 \le x, y \le 6)에 대하여, 윗면에 xx가 적힌 주사위의 개수와 윗면에 yy가 적힌 주사위의 개수는 서로 다르다.
  4. (33점) 추가 제약 조건 없음.

입력 형식

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

그다음 줄에는 NN개의 정수 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 공백으로 구분되어 차례대로 주어진다.

출력 형식

첫 줄에, 상훈이가 탑을 쌓는 방법을 적절히 정했을 때 만들어지는 탑의 수의 최솟값을 출력한다.

예제

예제 1

입력
4
3 3 5 4
출력
2

예제 2

입력
2
3 4
출력
1

예제 3

입력
5
1 1 6 1 1
출력
3

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2026년 2차 대회 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.