원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
주사위 탑 쌓기
원제: 주사위 탑 쌓기
문제
상훈이는 개의 정육면체 주사위를 가지고 있다. 주사위는 순서대로 번 주사위, 번 주사위, , 번 주사위라고 부른다.
모든 주사위의 각 면에는 이상 이하의 정수가 하나씩 적혀 있다. 하나의 주사위에서 서로 다른 두 면에 적힌 수는 항상 다르며, 서로 마주 보는 두 면에 적힌 수의 합은 항상 이다.
상훈이는 개의 주사위를 사용하여 주사위 탑 쌓기를 하려고 한다. 구체적인 과정은 다음과 같다.
- 바닥에 개의 주사위를 모두 굴린다.
- 각 주사위의 윗면에 적힌 수를 기록한다. 번 주사위부터 번 주사위까지 윗면에 적힌 수를 순서대로 이라고 한다.
- 바닥에 놓인 주사위 중 개 이상을 선택하여 책상 위에 새로운 탑 하나를 만든다. 주사위를 바닥에서 들어 옮길 수는 있지만, 주사위의 방향을 바꾸어서는 안 된다. 선택한 주사위들을 쌓는 순서는 자유롭게 정할 수 있고, 이 주사위들은 모두 수직으로 일렬로 쌓아야 한다. 이때, 서로 맞닿은 두 면에 적힌 수는 같아야 한다.
- 바닥에 남은 주사위가 없을 때까지 과정 3. 을 반복한다.
예를 들어, 주사위 탑 쌓기는 다음과 같이 진행될 수 있다.
- 상훈이가 바닥에 개의 주사위를 굴렸더니, 번 주사위부터 번 주사위까지 윗면에 적힌 수가 각각 , , , 였다.
- 상훈이는 바닥에서 번, 번, 번 주사위를 선택했다. 그 후, 아래에서부터 번, 번, 번 주사위 순서가 되도록 탑을 쌓았다. 번 주사위의 윗면과 번 주사위의 아랫면에는 모두 이 적혀 있으며, 두 면은 서로 맞닿아 있다. 또한, 번 주사위의 윗면과 번 주사위의 아랫면에는 모두 가 적혀 있으며, 두 면은 서로 맞닿아 있다.
- 상훈이는 바닥에 남아 있는 번 주사위를 선택하여, 주사위 하나로 이루어진 탑을 쌓았다.
- 바닥에 남은 주사위가 없으므로 주사위 탑 쌓기를 종료한다. 상훈이는 총 개의 탑을 만들었다.
상훈이는 탑을 쌓는 방법을 적절히 정하여, 만들어지는 탑의 수를 최소화하려고 한다. 개의 주사위를 굴린 후 각 주사위의 윗면에 적힌 수가 주어질 때, 만들어지는 탑의 수의 최솟값을 구하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 정수 에 대하여
부분문제
- (8점)
- (28점) 주사위의 윗면에 적힌 수는 또는 이다. 즉, 정수 에 대하여 또는 이다.
- (31점) 임의의 서로 다른 두 정수 , 에 대하여, 윗면에 가 적힌 주사위의 개수와 윗면에 가 적힌 주사위의 개수는 서로 다르다.
- (33점) 추가 제약 조건 없음.
입력 형식
첫 줄에 정수 이 주어진다.
그다음 줄에는 개의 정수 이 공백으로 구분되어 차례대로 주어진다.
출력 형식
첫 줄에, 상훈이가 탑을 쌓는 방법을 적절히 정했을 때 만들어지는 탑의 수의 최솟값을 출력한다.
예제
예제 1
4 3 3 5 4
2
예제 2
2 3 4
1
예제 3
5 1 1 6 1 1
3