[BOJ 24392] 백준 24392번 - 영재의 징검다리

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

1. 문제

$24392$. 영재의 징검다리 (2022 중앙대학교 CHAC Open Contest C번)

백준 24392번 - 영재의 징검다리 (https://www.acmicpc.net/problem/24392)

2. 풀이

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

$dp[i][j]$ = $(i, j)$ 유리에 도달하는 경우의 수

현재 $(i, j)$ 유리에 서 있다면, 이전 상태는 $(i - 1, j - 1),$ $\;(i - 1, j),$ $\;(i - 1, j + 1)$ 중 하나였을 것이다. 따라서 이들 값을 모두 더해주면 된다.

$dp[i][j]$ $ = dp[i + 1][j - 1]$ $\; + dp[i + 1][j]$ $\; + dp[i + 1][j + 1])$

1. 상좌우 끝 쪽에 빈 공간을 만들어서$(j=0, j=M+1, i=0)$ 예외처리를 일일이 하지 않아도 문제없이 수행할 수 있게 했다.

2. 세 수를 한 번에 더하면 integer 범위를 초과하므로, long long으로 선언했다.

3. 채점 결과

4. 회고

.

5. 코드