[백준/30677번] 반짝반짝 빛나는 별가루 - S3/Python

문제

스타는 별가루를 만드는 마법 연습을 하는 중이다. 본인의 실력을 시험하기 위해 하루에 한 번씩, 총 $N$일 동안 마법을 사용하여 별가루를 얼마나 만들 수 있는지 확인하고자 했고 $N$일 동안의 계획을 세웠다.

스타는 별가루를 만들 수 있는 $K$가지의 마법을 사용할 수 있다. 각각의 마법을 $1$번 마법, $2$번 마법, ... , $K$번 마법이라고 부르기로 하자.

 $i$번 마법을 사용해서 만들 수 있는 별가루의 개수는 다음과 같다.

$\Delta Stardust = \lfloor base_i(1+\frac{combo \cdot C}{100})(1+\frac{skill_i \cdot s_i}{100}) \rfloor$ 

식에 대한 설명은 다음과 같다.

• $\Delta Stardust$: 만들어진 별가루의 개수이다.
•  $base_i$: $i$번 마법을 사용해서 기본적으로 만들 수 있는 별가루의 개수이다.
•  $combo$: 연속으로 마법을 사용한 횟수이다. 예를 들어, 오늘 마법을 사용하기 전에 마법을 $5$일 연속으로 사용했다면 $combo = 5$이다.
•  $skill_i$: $i$번 마법의 숙련도이다. 예를 들어, 오늘 마법을 사용하기 전에 $i$번 마법을 사용한 경험이 $3$번 있으면 $skill_i = 3$이다.
• $C$와 $s_i$는 상수이다.

스타의 초기 피로도는 $0$이며, $i$번 마법을 사용할 때마다 스타의 피로도는 $p_i$만큼 상승한다. 피로도가 $100$을 초과하게 되면, 마법봉이 망가지고 이후에는 어떤 마법도 쓸 수 없게 된다. 동시에, 지금까지 만들었던 별가루도 못 쓰게 된다. 피로도는 휴식을 통해 줄일 수 있다. 휴식을 취하면 피로도가 $R$만큼 줄어들지만, 연속으로 마법을 사용한 횟수는 $0$이 된다. 피로도는 $0$ 미만으로 내려가지 않으며, 만약 휴식으로 감소하는 피로도가 현재 피로도보다 크다면 피로도는 $0$이 된다.

스타의 계획을 보고 $N$일 동안 만들 수 있는 별가루의 총 개수를 계산해 보자.

입력

첫째 줄에는 $N,K,C,R$ 이 공백을 사이에 두고 주어진다.$(1 \leq K \leq N \leq 100 \, 000;$ $1 \leq C \leq 100;$ 1≤𝑅≤100)$1 \leq R \leq 100)$ 

둘째 줄에는 $base_1, \cdots , base_K$가 공백을 사이에 두고 주어진다.$(1 \leq base_i \leq 100 \, 000)$ 

셋째 줄에는 $s_1, \cdots , s_K$가 공백을 사이에 두고 주어진다. $(1 \leq s_i \leq 100)$ 

넷째 줄에는 $p_1, \cdots ,p_K$가 공백을 사이에 두고 주어진다. $(1 \leq p_i \leq 100)$ 

다섯째 줄부터 $N$개의 줄에 걸쳐 스타가 $i$번째 날에 사용하려고 계획한 마법의 번호 $l_i \ (0 \leq l_i \leq K)$가 한 줄에 하나씩 주어진다. $l_i$가 $0$이면 그날 하루는 휴식을 취한다는 뜻이다.

입력으로 주어지는 모든 수는 정수이다.

풀이

from math import floor
N, K, C, R = map(int, input().split())
base = [0] + list(map(int, input().split()))
s = [0] + list(map(int, input().split()))
p = [0] + list(map(int, input().split()))
skill = [0]*(K+1)
combo = 0
stardust = 0
fatigue = 0
for _ in range(N):
    current = int(input())
    if current == 0:
        combo = 0
        fatigue = max(fatigue - R, 0)
        continue
    stardust += base[current]*(100+combo*C)*(100+s[current]*skill[current])//10000
    skill[current] += 1
    combo += 1
    fatigue += p[current]
    if fatigue > 100:
        print(-1)
        break
else:
    print(stardust)

해결방법

간단한 구현 문제이지만 아래 사항을 고려하여 문제 풀이를 진행해야 함.

1. 피로도가 회복될 경우 피로도는 0으로 내려가지 않는다는 점.
2. skill 사용 횟수를 기록하여 스킬 숙련도를 수식에 적용할 것.
3. 주어진 수식의 소숫점 계산 과정에서 문제가 발생할 수 있으므로 소수점 계산 방식을 변경할 것.

위 세가지를 고려하여 구현을 진행하면 문제 해결 가능.