아름이는 주사위 N개를 가지고 있다. 주사위는 정육면체 모양이고, 크기는 N개 모두 동일하다. 일반적인 주사위와 다르게, 여섯 개의 면에는 정수가 하나씩 쓰여 있다. 한 주사위에는 모두 같은 정수가 쓰여 있다.
주사위 탑이란 주사위를 위로 쌓은 모양을 의미한다. 주사위를 쌓을 때는 주사위의 변이 일치하게 쌓아야 한다. 주사위 N개를 쌓아서, 주사위 탑의 개수를 최소로 하려고 한다.
주사위에 쓰여 있는 수를 s라고 했을 때, 그 주사위의 위에는 최대 s개의 주사위를 올려놓을 수 있다.
예를 들어, 주사위가 총 4개 있고, 각 주사위에 쓰여 있는 수가 1, 2, 4, 5인 경우를 생각해보자. 주사위를 쌓은 결과가 위에서부터 2, 1, 4, 5인 경우는 가능하다. 2가 적힌 주사위 위에 0개, 1이 적힌 주사위 위에 1개, 4가 적힌 주사위 위에 2개, 5가 적힌 주사위 위에 3개가 있기 때문이다. 하지만, 4, 1, 5, 2의 순서로 쌓는 것은 불가능하다. 2가 적힌 주사위의 위에 주사위가 총 3개 있기 때문이다.
주사위의 개수 N과 각 주사위에 쓰여 있는 수가 주어졌을 때, 만들 수 있는 주사위 탑의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 주사위의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 주사위에 쓰여 있는 수가 주어진다. 주사위에 쓰여 있는 수는 1,000보다 작거나 같은 양의 정수 또는 0이며, 공백으로 구분되어져 있다.
출력
첫째 줄에 만들 수 있는 주사위 탑의 최소 개수를 출력한다.
예제 입력 1
4
1 2 4 5
예제 출력 1
1
예제 입력 2
4
1 2 1 2
예제 출력 2
2
예제 입력 3
5
0 0 0 0 0
예제 출력 3
5
어렵다... 결국 열심히 찾아봤으나 블로그에도 별로 나와있지 않는 문제였다.
분명 그리디 또는 DP 스럽다고 생각은 들었는데 역시 그리디 였고
나는 그리디가 약하다...
접근 방법: 주사위에 쓰여 있는 수의 범위가 0~1000까지이다. 0이라고 쓰여있는 주사위는 자기 자신 위에는 아무것도 올 수 없으므로, 주사위 탑을 만들때 가장 우선적으로 와야 한다. 그렇지 않으면, 개별적으로 0으로 된 주사위 탑을 따로 생성해야하므로 동률이거나 손해다. 1이라고 쓰여있는 주사위는 주사위 탑을 만들 때 그 다음으로 우선적으로 와야한다. 0이라는 주사위가 없다면, 1이라는 주사위를 최대한 소모하는 것이 좋다. 이후 주사위탑을 생성할 때에도, 마찬가지이다. 이 규칙을 지키며 주사위탑을 생성하면 된다.
def solution(N, dice):
dice.sort()
ans = 0
height = 0
new_tower = True
while dice:
flag = True
for i in range(len(dice)): # 가장 작은 값의 주사위부터 시작
if dice[i] >= height:
if new_tower: # 우리는 탑의 개수를 구하는 것이므로 새로운 탑에서 주사위를 쌓을 수 있으면
ans += 1 # 탑 한개 추가
del dice[i]
height += 1
new_tower = False # 탑 한개 추가 했으니
flag = False
break # 한번이라도 if조건을 만족하면 한번만 확인하고 끝냄
# 주사위를 다 돌면서 해당 조건을 한번도 만족하지 못했다면
# 새로운 주사위 탑을 쌓는다.
if flag:
height = 0
new_tower = True
return ans
if __name__=="__main__":
N = int(input())
dice = list(map(int, input().split()))
print(solution(N,dice))
우선순위 큐, 힙큐로 풀기
import heapq
def solution(dices):
# 주사위 값을 정렬된 순서로 관리하기 위해 최소 힙을 사용
heapq.heapify(dices)
towers = [] # 각 탑의 맨 위에 있는 주사위 값들을 저장할 리스트
while dices:
dice = heapq.heappop(dices) # 가장 작은 값을 하나 꺼냄
placed = False # 주사위를 쌓았는지 여부
for i in range(len(towers)): # 현재 주사위는 dice값만큼의 주사위 개수를 쌓을 수 있음,
if towers[i] <= dice: # 현재 쌓은 주사위 개수 towers[i]보다 현재 주사위 dice 값이 더 크다면
towers[i] += 1 # 탑의 높이를 증가시킴
placed = True # 주사위를 쌓았음을 표시
break
# 만약 지금까지 쌓은 탑의 주사위 개수가 현재 주사위 dice 값보다 더 많이 쌓여 있다면
if not placed:
# 새로운 탑을 만듦
towers.append(1)
return len(towers)
if __name__=="__main__":
# 입력 받기
N = int(input())
dices = list(map(int, input().split()))
# 결과 출력
print(solution(dices))