[그리디 알고리즘 Lv.02] 25496번 장신구 명장 임스 (Python)

1. 문제

    25496번 장신구 명장 임스

    (https://www.acmicpc.net/problem/25496)

 

메이플스토리에는 전문 기술이라는 제작 시스템이 있다. 전문 기술은 특정량의 피로도가 쌓이는 대신 다양한 장비 및 비약을 제작할 수 있는 시스템이다. 장신구 명장인 임스는 어떻게 하면 더 효율적으로 많은 장신구를 제작할 수 있을지 고민에 빠졌다.

임스가 만들 수 있는 장신구는 N개가 있고, 각각의 장신구를 만들면 A만큼의 피로도가 누적된다.

피로도가 200 미만인 경우, 장신구를 제작할 수 있다. 현재 쌓인 피로도가 P일 때, 임스가 제작할 수 있는 장신구의 최대 개수를 구해보자!

 

 

2. 문제 포인트

• 만들 수 있는 개수 한정 (N)
• 각 장신구마다 A만큼의 피로도 누적
• 피로도가 200미만이면 제작 가능
  199일때 피로도 100이 누적되는 장신구도 제작 가능
  시작 시점에서 200미만이면 됨
• 최대 개수 구하기

 

반응형

 

3. 접근법

• 가장 최대 제작 개수가 중요 (피로도에 따른 가중치 없음)
  입력 받은 장신구별 피로도 증가량을 오름차순으로 정렬 후 사용
  

  

 

 

4. 결과 코드

import sys

a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))

# 각 아이템별 소모 피로도를 오름차순 정리
b = sorted(b)

cnt = 0

# 전체 횟수 a[1]만큼 반복
## 제한 없이 while True문을 사용할 경우 예외 발생
## ex. 10피로도 2개 아이템 (1, 2) 
for n in range(a[1]):
    # 현재 피로도가 200이상인지 확인하여 True인 경우 for문 종료
    if a[0] >= 200:
        break

    # a[0](현재피로도)에 가장 작은 b값 순차적으로 덧셈
    a[0] = a[0] + b[cnt]
    cnt += 1
    
print(cnt)

# https://www.acmicpc.net/problem/25496