[Python] 15703번 주사위 쌓기

 

 

https://www.acmicpc.net/problem/15703

15703번: 주사위 쌓기

---

 

23/05/25

 

 

구현을 조금 요하는 그리디 문제이다.

---

 

문제 접근 방식:

 

 

문제 요약을 하면 다음과 같다.

 

주사위가 주어져 있고, 하나의 주사위의 모든 면에는 같은 눈금이 적혀있다.

 

이런 주사위들을 모아 주사위 탑을 쌓고자 하는데, 한 주사위에 적힌 눈금이 $5$라면, 그 주사위 위에는 $5$개를 넘어서 주사위를 쌓을 수 없다고 한다.

 

이럴 때, 주사위 탑의 최소 개수를 구하는 것이 우리의 목적이다.

 

 

 

우선 관찰을 해보면, $0$이라고 쓰인 주사위는 자기 자신 위에는 아무것도 올 수 없으므로, 어떤 주사위 탑을 만든다고 하면 항상 최우선적으로 맨 위에 놓여있어야 하고, 가장 먼저 쓰여야 한다는 사실을 자명하게 알 수 있다.

 

그렇지 않다면, 개별적으로 $0$이 쓰인 주사위 탑을 새롭게 하나 만들어야 되므로 동률이거나 손해이다.

 

마찬가지로, $1$이라고 적힌 주사위 또한, 자기 자신 위에 $1$개의 주사위 밖에 오지 못하므로, 어떤 주사위 탑을 만든다고 하면 $0$이라고 적힌 주사위 다음으로 우선적으로 쓰여야 함을 알 수 있다.

 

이후 눈금들도 같은 규칙을 적용받음을 알 수 있다.

 

 

이 규칙을 그대로 구현하면 문제를 해결할 수 있다.

 

예를 들어, $1$이 $5$개, $2$가 $3$개, $3$이 $4$개 주어진다고 하면, 다음과 같이 주사위 탑들을 구성해야 함을 알 수 있다.

 

$tower_1 : (1, 1)$

$tower_2 : (1, 1)$

$tower_3 : (1, 2, 2)$

$tower_4 : (2, 3, 3, 3)$

 

따라서 탑의 최소 개수는 $4$개가 된다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 15703번 주사위 쌓기
# 구현, 그리디
'''
접근 방법:
주사위에 쓰여 있는 수의 범위가 0~1000까지이다.
0이라고 쓰여있는 주사위는 자기 자신 위에는 아무것도 올 수 없으므로,
주사위 탑을 만들때 가장 우선적으로 와야 한다.
그렇지 않으면, 개별적으로 0으로 된 주사위 탑을 따로 생성해야하므로 동률이거나 손해다.
1이라고 쓰여있는 주사위는 주사위 탑을 만들 때 그 다음으로 우선적으로 와야한다.
0이라는 주사위가 없다면, 1이라는 주사위를 최대한 소모하는 것이 좋다.
이후 주사위탑을 생성할 때에도, 마찬가지이다.
이 규칙을 지키며 주사위탑을 생성하면 된다.

가장 최적의 주사위 탑의 모양은 다음과 같다.
주사위 눈금
0 1 2 3 4 5 6 ...
주사위의 총 개수
1 2 3 4 5 6 7

이런 모양을 따르며 주사위 탑을 생성하면 된다.
'''
import sys
input = sys.stdin.readline

dice = [0 for _ in range(1001)]  # 인덱스: 주사위의 눈 / 값: 그 주사위가 몇개인가.
N = int(input())
for d in map(int, input().rstrip().split()):
    dice[d] += 1

dice_tower = 0  # 주사위 탑의 총 개수
while True:
    if sum(dice) == 0:
        print(dice_tower)
        break
    dice_num_in_dice_tower = 0  # 주사위 탑 안에 있는 주사위의 개수
    for d in range(1001):  # 주사위 탑 생성할 때 dice 배열에서 하나씩 빼서 만들자.
        if dice[d] == 0:
            continue
        else:
            while True:
                dice[d] -= 1
                dice_num_in_dice_tower += 1
                if dice_num_in_dice_tower > d+1:
                    dice[d] += 1
                    dice_num_in_dice_tower -= 1
                    break
                if dice[d] == 0:
                    break
    dice_tower += 1