Python3
문제
https://www.acmicpc.net/problem/20413
키워드
- 그리디 알고리즘
문제 풀이
문제 요구사항
MVP 등급은 브론즈(B), 실버(S), 골드(G), 플래티넘(P), 다이아몬드(D)로 총 다섯 등급이 있으며, 현재 달과 지난달, 즉 현재 달을 포함한 최근 2개월간의 과금액으로 결정된다.
단, 단풍잎이야기에는 과도한 과금을 막기 위해 '최대 과금 한도'가 있어 한 달에 최대 다이아몬드 등급 기준액 까지만 과금할 수 있으며, 만원 단위로만 과금이 가능하다.
MVP 등급은 해당 달이 끝날 때 계산되어 책정된다.
상민이의 여자친구는 상민의 과금액을 역추적하기 위해 상민이가 게임에 최대 얼마나 과금한건지 알려달라고 부탁했다.
변수 및 함수 설명
- n: 게임을 플레이 한 개월 수 (1 ≤ N ≤ 36)
- s, g, p, d: 실버, 골드, 플래티넘, 다이아몬드 등급 기준액 s, g, p, d가 만원 단위로 순서대로 주어진다. 브론즈 등급 기준액은 0 원이다.
(0 < s < g < p < d ≤ 500) - grade: 게임을 플레이 한 첫 번째 달부터 N 번째 달까지의 MVP 등급 (기록과 같은 MVP 등급 달성이 불가능한 경우는 주어지지 않는다.)
- total: 입력된 MVP 등급을 달성하기 위한 최대 누적 과금액
- prev: 이전달 과금액
제한 사항
상민이가 한번 달성한 MVP 등급은 줄어들지 않는다.
풀이
(입력 및 선언)
- 게임을 플레이 한 개월 수와 등급 기준액을 입력받는다.
- 게임의 MVP 등급을 입력 받고, total과 prev 변수를 0으로 초기화한다.
(최대 누적 과금액 계산하기)
-
총 n번 반복한다.
-
최대 누적 과금액은 다음 등급 - 1한 값에 전 달의 과금액을 뺀 것과 같다.
-
전 달 과금액은 다음 등급 - 1한 값에 전 달 과금액을 뺀 값이다.
1번 예시처럼 등급 기준액은 30, 60이고 등급이 BS일 때,
첫 번째 달은 29, 두 번째 달은 29(prev) + x = 59가 된다.
즉, x는 30이다.
이렇게 전 달의 과금액과 등급 기준액을 비교하면서 최대 누적 과금액을 구할 수 있다. -
마지막 다이아몬드 레벨의 최대 금액은 total과 prev 모두 다이아몬드 기준액이다.
최종 코드
n = int(input())
s, g, p, d = map(int, input().split())
grade = list(map(str, input()))
total = 0
prev = 0
for i in range(n):
if grade[i] == 'B':
total += s - 1 - prev
prev = s - 1 - prev
elif grade[i] == 'S':
total += g - 1 - prev
prev = g - 1 - prev
elif grade[i] == 'G':
total += p - 1 - prev
prev = p - 1 - prev
elif grade[i] == 'P':
total += d - 1 - prev
prev = d - 1 - prev
elif grade[i] == 'D':
total += d
prev = d
print(total)피드백
과금액을 모르는 상태에서 전 달을 같이 처리해주는 부분이 어려워 블로그를 참고했다.
그리고 다이아몬드 등급에서 다이아 등급액을 넣어주어야 하는 부분도 주의 깊게 살펴봐야 했다.
