songgj123   6년 전

일단 제 생각은 DP입니다.

cache[i][j][4]의 배열을 선언합니다.

배열의 의미는

좌표 (i, j)가 k번째로 저장됐을 때, 최대값입니다.

이게 성립한다고 생각한 이유는

i, j가 k번째로 더해져서 최대값이 되려면

주변 네 방향에서의 k-1번째 값 중에 최대값을 선택하면 되기 때문입니다.

그런데 이걸 직접 구현하니 칸을 반복해서 방문하는 경우가 생기더군요

일단 코드를 제외하더라도 제가 한 생각이 맞는지 궁금하네요

참고로

모든 모양을 배열로 저장해서 제출해보니 정답 나오네요....

혹시나 이게 진짜 풀이법은 아니겠죠??

다른 방식으로 푸신 분 댓글로 좀 알려주세요ㅜㅜ

exqt   6년 전

생각하신 방법으론 중복된 원소를 빼주기가 힘들거 같습니다.

19개 모양 전부 만드셔서 푸셔도 되고 정해는 아마 dfs로 깊이 4까지 모두 탐색하고 ㅜㅏㅗㅓ 모양은 따로 처리하는 방식일듯 합니다.

댓글을 작성하려면 로그인해야 합니다.