| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 113 | 49 | 27 | 38.028% |
Albert는 혼자 할 수 있는 던전 게임을 고안했다. 이 게임은 1차원상에서 진행되며, $0$번 방 부터 $N$번 방까지 순차적으로 "용사"를 움직이며 진행한다. $0$번 방에는 용사가 있으며 용사의 처음 체력을 $X$라 하자 (이 값은 Albert가 추후에 정하는 값이다).
$1$번 부터 $N$번 방까지 각 방에는 몬스터가 하나 있고 몬스터는 마법 주문서 하나를 지키고 있다. $i$번째 방의 몬스터와 싸우면 용사의 체력은 $D_i \gt 0$ 만큼 깎이는데, 만약 용사의 체력이 0이하가 되면 용사가 패배한다. 몬스터를 물리친 이후 그가 지키고 있던 주문서를 이용하면 체력을 올릴 수 있다. $i$번째 방의 주문서는 "덧셈주문서" 이거나 "곱셈주문서"인데, 양의 정수 $R_i$가 적혀 있다. 편의상 문자열 $S$가 입력으로 주어지며, $S_i$가 $i$번째 주문서의 종류를 나타낸다고 하자.
+' 이고, 이 주문서를 사용하면 용사의 체력이 $R_i$ 만큼 올라간다.*' 이고, 이 주문서를 사용하면 용사의 체력이 $R_i$ 배로 올라간다.Albert는 용사의 처음 체력이 $X$인 상태로 시작하여 $0$번 방에서 각 방을 순서대로 지나 $N$번 방의 몬스터까지 물리치는 것이 목표이다. 이 때 $i$번째 방에서 몬스터를 물리치고 얻은 주문서는 반드시 즉시 사용해야한다.
예를 들어 $N = 4$, $D = [5, 10, 15, 20]$, $S =$ "+*++", $R = [2, 3, 4, 5]$ 인 경우를 생각해보자.
위의 예제의 경우 처음 용사의 체력이 24미만이면 모든 몬스터를 물리칠 수 없지만 24이상이면 모든 몬스터를 물리칠 수 있음을 보일 수 있다.
입력으로 던전에 대한 정보인 $N, D, S, R$이 주어졌을 때, 모든 몬스터를 물리치기 위해 필요한 용사의 처음 체력의 최솟값을 구해보자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N$이 주어진다. 둘째 줄에는 $N$개의 양의 정수가 공백으로 구분되어 주어지는데 이는 $D_1, D_2, \dots, D_N$을 나타낸다. 셋째 줄에는 길이 $N$인 문자열 $S$가 공백없이 주어지는데 이는 각 주문서의 보상 종류는 타나낸다. 각 문자는 '+' 혹은 '*'이다. 넷째 줄에는 $N$개의 양의 정수가 공백으로 구분되어 주어지는 이는 $R_1, R_2, \dots, R_N$을 나타낸다.
각 테스트 케이스의 정답을 각 줄에 출력한다.
+' 혹은 $S_i$ = '*' (따옴표 제외)7 4 5 10 15 20 +*++ 2 3 4 5 4 3 5 3 5 +**+ 5 2 2 4 3 2023 2023 2023 *** 1 2 3 3 2023 2023 2023 *** 3 2 1 3 1000 1000 1000 +++ 1 1 1 3 1000 1000 1000 *** 1 1 1 3 10 10 10 *** 100000000 100000000 100000000
24 6 5058 3035 2999 3001 11
예제 1: 본문에서 다루었다.
예제 2: 용사의 체력은 0번방부터 몬스터를 물리치고 주문서를 사용한 순서대로 6 -> 3 -> 8 -> 3 -> 6 -> 3 -> 6 -> 1 -> 5가 된다. 이보다 더 낮은 체력으로 모든 몬스터를 물리칠 수 없다.
예제 3-6: 추가 설명 없음.
예제 7: 11의 체력으로 시작하면 1번 방의 주문서를 사용한 후 체력이 $10^8$이 된다. 이후 2번 방의 주문서를 사용한 후 체력은 $(10^8 - 10) \cdot 10^8 = 10^{16} - 10^{9}$이 된다. 3번 방의 몬스터를 물리치고 주문서를 사용하면 최종 체력은 $10^{24} - 10^{17} - 10^{9}$이 된다. 11보다 더 낮은 체력으로 시작하면 1번 방의 몬스터를 물리칠 수 없다.
© 2026 주식회사 데이원컴퍼니. All Rights Reserved.