[BOJ 24884] 백준 24884번 - 장작 넣기

		2022 숭고한 연합 알고리즘 콘테스트 Open Contest 풀이
A		[BOJ 24883] 자동완성
B		[BOJ 24884] 장작 넣기
C		[BOJ 24885] 주식
D		[BOJ 24886] SKH 문자열
E		[BOJ 24887] 최대한의 휴식
F		[BOJ 24888] 노트 조각
I		[BOJ 24891] 단어 마방진

1. 문제

$24884$. 장작 넣기 (2022 숭고한 연합 알고리즘 콘테스트 B번)

백준 24884번 - 장작 넣기 (https://www.acmicpc.net/problem/24884)

2. 풀이

$N\leq 6$이고, 각 시각마다 취할 수 있는 행동은 총 세 가지가 있다.

1. 현 위치에 그대로 머무른다.
2. 왼쪽으로 이동한다.
3. 오른쪽으로 이동한다.

따라서 총 $3^6=749$ 개의 경우의 수가 생기기 때문에, 브루트포스를 돌리면 시간 내에 충분히 돌아간다.

---

DFS는 이런식으로 구현하였다.

1. 현재 화력 정보를 토대로 각 모닥불의 화력이 얼마나 감소할지를 조사하여 vector<int> dec에 담는다. 단, 현재 위치는 이전 시각에 장작을 넣었으므로, 화력에 변화가 없다.
2. F[i]를 dec[i]만큼 감소시킨다.
3. 시각이 $T$인 경우, 켜져 있는 모닥불의 수가 $K$이상인지 조사한다. 시각이 $T$가 아닌 경우, 위에서 서술한 세 가지 행동 각각에 대해서 다음 DFS로 넘어간다.
4. F[i]의 값을 원래대로 되돌리기 위해, F[i]를 dec[i]만큼 증가시킨다.

---

이때, 주의할 점이 두 가지 있다.

• 화력이 $0$ 이상이라 F[i]의 최저값을 0으로 제한해버리면, 위에서 구현2를 하고 구현4를 했을 때, 원래 값으로 되돌아오지 않는다.
• 시각이 $T$일때도 모든 작업이 끝나면 구현4를 수행하여 F[i]의 값을 원래대로 되돌려야 한다.

3. 채점 결과

4. 회고

시각이 $T$일때 F[i]의 값을 빼기 전에 함수를 종료시켜버려서 값을 원래대로 되돌리지 못해 WA를 한 번 받았다.

DFS가 다 끝나면, 모든 변수들을 원래대로 되돌렸는지 다시 한 번 확인하는 습관을 들여야겠다.

5. 코드