[AC] 2186 문자판

출처 : https://www.acmicpc.net/problem/2186

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/2186.cpp

이 문제는 과거 오답을 맞았다가 다시 도전해서 정답을 맞은 문제이다.

이 문제도 뭐 별거 없어보이지만 최대 움직이는 칸이 정해져있어 그 안에서 자유롭게 이동이 가능하다.

즉 일반적인 DFS로는 풀 수 없다. 왜냐면 사용한 녀석을 다음 녀석이 또 사용할 수 있기 때문이다.

그래서 생각한게 3차원배열과 DP이다. 

먼저 배열의 입력을 받고 dp배열을 3차원으로 만든다.

2차원은 그냥 입력과 동일한녀석이고 3차원이 되면서 글자의 개수를 의미하게 된다.

그리고 하나의 점마다 모두 계산해본다. 

dp+dfs에서는 패턴이 정해져있다. 해당 녀석이 존재하면 리턴하고 존재하지않으면 갱신하는 방식이다.

나는 각 점을 검사하면서 글자수를 할당시켰고 최종적으로 갱신 후 리턴하는 방식을 사용했다. 

이와 비슷한 문제로 1005번? ACM craft(위상정렬)와 이분매칭알고리즘이 있다.

간혹 햇갈리는 부분이 있다면 dp가 존재할때 새로이 갱신할때가 있는데 이는 dp가 존재한다고 리턴할때가 아니라, dp를 토대로 새로운 경우를 조사할때이다. 근데 이것은 그런경우가 아니라, 그냥 해당 구간에 몇개가 조사되었는지 알아내고 그걸 다시 사용하기만 하면 되는 경우이다. 

즉, 최대값을 구하는것인지 아니면 가짓수를 갱신하는지 여기에 초점을 맞추면 된다.