(JAVA) 백준 21317번 : 징검다리 건너기 -- [DFS]

https://www.acmicpc.net/problem/21317

21317번: 징검다리 건너기

 

안녕하세요.

 

이 문제는 간단합니다.

 

 

DFS를 사용하여 

 

1) 작은 점프(1칸 이동)

2) 큰 점프(2칸 이동)

3) 매우 큰 점프(3칸 이동) -> 1번만 사용 가능

 

각각의 경우에 DFS로 재귀호출하면 됩니다.

 

 

그래서 

각 돌에서 작은점프, 큰점프하는 데 드는 에너지를 2차원 배열[n][2]로 저장해두고 (0: 작은점프 / 1: 큰점프)

DP 2차원배열[n][2]을 별도로 만들어 해당 돌에 도착했을 때의 에너지 최소 값을 저장해둡니다.

(0: K점프 안한경우 / 1: K점프 한경우) 

 

DP 초기값(0)인 경우만 구분해서 잘 넣어주시면 

DP[n][0]과 DP[n][1] 중 적은 값을 출력하면 끝납니다.

** 이 때, 초기값을 MAX_VALUE로 설정해둬도 됩니다.

 

 

 

감사합니다.

 

 

소스코드

---