최근 추가된 문제들저장한 문제문제집

카테고리 DLC 대회 그룹 팀 게시판

문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹

문제 제안로그인 회원가입

DOJ

OI 서브태스크 채점, Elo 레이팅, Discord 인증을 갖춘 커뮤니티 온라인 저지.

문제

문제 목록 카테고리

커뮤니티

대회 랭킹 게시판 공지사항 외부 대회 개최 이용 안내

계정

로그인 회원가입 채점 현황

정책

이용약관 DLC 이용 규칙 개인정보 처리방침 API 사용 설명서 언어별 채점 환경 대회 순위 보상 레이팅과 퍼포먼스

© 2026 DOJ

모든 권리 보유

해설

루미의 스트레스 해소하기

문제로 돌아가기

해설

DP 문제입니다. $dp[t][s]$ 를 $t$ 분이 지났고 체력을 $s$ 이하로 썼을 때 스트레스의 최솟값으로 둡니다.
처음에는 취미를 하나도 하지 않은 경우로 채웁니다: $dp[t][s] = A + tF$ .
$t$ $t$ , $s$ $s$ 를 $1$ $1$ 부터 늘려 가며, 각 취미(해소량 $L$ $L$ , 소모 시간 $H$ $H$ , 체력 소모량 $M$ $M$ )에 대해 갱신합니다.
- $t \geq H$ 이고 이면 취미를 시작할 때의 체력은 이고, 이 값으로 를 구합니다.

dp[t][s] = \max(0,\ \min(dp[t][s],\ dp[t][s-1],\ dp[t-1][s] + F,\ dp[t-H][s-M] - L_{eff}))

그 취미를 할 수 없으면 마지막 항만 빼고 갱신합니다.

dp[t][s] = \max(0,\ \min(dp[t][s],\ dp[t][s-1],\ dp[t-1][s] + F))

같은 취미를 여러 번 할 수 있으므로 $dp[t-H][s-M]$ 은 같은 표의 값을 그대로 씁니다.
답은 $dp[B][C]$ 입니다.
주의할 점
- 취미를 즐기지 않는 동안에는 $1$ 분마다 스트레스가 씩 오릅니다.

t \ge H

t \geq H

s \ge M

C - (s - M)

L_{eff}

0

,

min

(

d

p

[

t

]

[

s

]

,

d

p

[

t

]

[

s

−

1], dp[t−

1][s]+

F, dp[t−

H][s−

M]−

Leff))

]

,

d

p

[

t

]

[

s

−

1], dp[t−

1][s]+

F))

1

F

E > 100

이면

L_{eff}

가 음수가 됩니다. 음수를 양수로 나눈 결과는 언어마다 다르니 주의합시다. 지문의

L_{eff}

는 내림입니다.

스트레스의 최솟값은

0

입니다.

시간복잡도는

\mathcal{O}(NBC)

, 공간복잡도는

\mathcal{O}(BC)

입니다.