[알고리즘][동적 계획법] 이동하기(백준)

다이나믹(동적 계획법) 알고리즘 문제 : 이동하기 (백준)

다른 알고리즘에 비해 동적 계획법이 상당히 어렵게 느껴집니다.

그만큼 공부량이 적었다는 반증이기도 하지만, 알고리즘 자체가 어려운 것도 사실입니다.

때문에 항상 다이나믹 알고리즘은 쉬운 문제를 골라서 풀어보았는데

이번에도 그리 난이도가 높은 문제는 아닙니다. 

동적 계획법의 기초중의 기초라 말할 수 있는 문제입니다.

동적 계획법 문제 : 이동하기 (백준)

01. 변수 선언 및 초기화

02. 다이나믹

다이나믹 (동적 계획법) 알고리즘의 핵심은

1. 처음부터 차곡차곡 답을 쌓아 나간다.

2. 저장한 답을 바탕으로 현재의 답을 찾아 나간다.

위의 두가지 핵심을 잘 기억하고 있다면 이 문제는 상당히 쉽게 풀릴 것입니다.

--> 현재의 위치에서 바로 전에 들릴 수 있는 3개의 지점에서의 최대값을 비교합니다.

--> 바로 전에 들릴 수 있는 3개의 지점은 지금까지의 최대값을 저장해왔기 때문에 비교만 해준다면 답을 구할 수 있습니다.

--> 이동 방향은 오른쪽, 밑, 대각 이 세가지 뿐이기 때문에 바로 전에 거쳐온 지점은 현재 지점에서 왼쪽, 위쪽, 10시방향 대각선 위가 될 수 있겠네요.

다른 알고리즘 문제와는 다르게 동적 계획법은 꾸준히 풀지않으면 감이 떨어지는 듯한 느낌이 듭니다.

앞서 말씀드렸듯이 그만큼 동적 계획법의 공부량이 비교적 적었기 때문이기도 하겠지요.

좀 더 분발해야 할 것 같습니다.