[BOJ 24390] 백준 24390번 - 또 전자레인지야?

		2022 중앙대학교 CHAC 풀이
A		[BOJ 24389] 2의 보수
B		[BOJ 24393] 조커 찾기
C		[BOJ 24392] 영재의 징검다리
D		[BOJ 24390] 또 전자레인지야?
E		[BOJ 24395] 명진이의 신년계획

1. 문제

$24390$. 또 전자레인지야? (2022 중앙대학교 CHAC Open Contest D번)

백준 24390번 - 또 전자레인지야? (https://www.acmicpc.net/problem/24390)

2. 풀이

현재 상태가 과거의 어떤 여러 상태들에 의해 결정되고, 이와 같은 작업이 누적되므로 DP(dynamic programming)을 생각할 수 있다.

현재 상태를 결정하는 요소는 총 두 가지가 있다. (1) 조리 시간 (2) 조리 중 여부

배열의 공간을 최소화하기 위해서, 조리시간이 항상 $10$의 배수인 점을 이용하여, 모든 시간을 $10$으로 나누어 생각하였다. $(10초\rightarrow 1,\;$ $ 60초\rightarrow 6,\;$ $ 300초\rightarrow 30)$

$dp[i][0]$ = 조리 시간이 총 $i \times 10$초이고, 조리 중이 아닐 때, 버튼을 누른 횟수

$dp[i][1]$ = 조리 시간이 총 $i \times 10$초이고, 조리 중일 때, 버튼을 누른 횟수

현재 상태에서 결정할 수 있는 행동(다음 상태로 넘어가기 위한 작업)은 총 여섯 가지가 있다.

1. $10$초 버튼 누르기 $\rightarrow i = i + 1$
2. $1$분 버튼 누르기 $\rightarrow i = i + 6$
3. $10$분 버튼 누르기 $\rightarrow i = i + 60$
4. 조리 중이 아니고$(j=0)$, 조리시간이 $0$초일 때$(i=0)$, 조리시작 버튼 누르기 $\rightarrow i = i + 3$, 조리 상태가 조리 중으로 바뀜$(j=1)$
5. 조리 중이 아니고$(j=0)$, 조리시간이 $0$초가 아닐 때$(i=0)$, 조리시작 버튼 누르기 $\rightarrow$ 조리 상태가 조리 중으로 바뀜$(j=1)$
6. 조리 중일 때$(j=1)$, 조리시작 버튼 누르기 $\rightarrow i = i + 3$

이 행동들을 기반으로 재귀적 DP를 구현하면 된다. 정확히 시간을 맞춰야 하므로, 주어진 조리시간을 넘기면 INF를 return하며, 주어진 조리 시간을 정확히 맞추면 조리 상태에 따라서 적절한 값을 return한다. (조리 중이 아니면$(j=0)$, 조리 상태로 만들어야 하므로 횟수가 $1$ 증가함)

3. 채점 결과

4. 회고

조리 중이 아니면서 조리시작 버튼을 누른 경우에서, ‘조리시간이 $0$초인 경우’를 예외처리 하지 않아 WA를 받았다.

5. 코드