백준 20937번: 떡국(그리디)

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

20937번: 떡국

INPUT: N개의 떡국 그릇을 제공 // 떡국 그릇의 크기(정수)

OUTPUT: 쌓을 수 있는 최소 그릇탑의 갯수

그릇의 크기가 더 큰 것 위에만 작은 것을 올릴 수 있음. 탑의 갯수가 최소라는 것은, 최대한 높이 쌓았을 때 가능함.

 

def solve(N, items):
    items = sorted(items, reverse = True)
    cnt = 0
    tops = {i:0 for i in range(len(items))}
    now_top = 0
    tops[0] = items[0] # 가장 첫번째 탑에, 가장 큰 그릇을 깔아둠
    for i in range(1, N):
        if items[i]==items[i-1] :
            now_top += 1
            # 이전과 같으면 다음 탑에
            tops[now_top] = items[i]
        else:
            # 이전과 같지 않으므로, 적어도 0번째 탑에 있는 마지막 그릇보다는 작은 그릇임.
            now_top = 0
            tops[now_top] = items[i]
    tops = [x for x in tops.values() if x!=0]
    return len(tops)

if __name__=='__main__':
    N = int(input())
    items = list(map(int,input().split()))
    print(solve(N, items))

 

https://wannabe00.tistory.com/entry/백준-13305-주유소그리디 에서 배웠던 아이디어를 열심히 적용해보고 있다.