14500번 - 테트로미노
일단 제 생각은 DP입니다.
cache[i][j][4]의 배열을 선언합니다.
배열의 의미는
좌표 (i, j)가 k번째로 저장됐을 때, 최대값입니다.
이게 성립한다고 생각한 이유는
i, j가 k번째로 더해져서 최대값이 되려면
주변 네 방향에서의 k-1번째 값 중에 최대값을 선택하면 되기 때문입니다.
그런데 이걸 직접 구현하니 칸을 반복해서 방문하는 경우가 생기더군요
일단 코드를 제외하더라도 제가 한 생각이 맞는지 궁금하네요
참고로
모든 모양을 배열로 저장해서 제출해보니 정답 나오네요....
혹시나 이게 진짜 풀이법은 아니겠죠??
다른 방식으로 푸신 분 댓글로 좀 알려주세요ㅜㅜ
생각하신 방법으론 중복된 원소를 빼주기가 힘들거 같습니다.
19개 모양 전부 만드셔서 푸셔도 되고 정해는 아마 dfs로 깊이 4까지 모두 탐색하고 ㅜㅏㅗㅓ 모양은 따로 처리하는 방식일듯 합니다.
댓글을 작성하려면 로그인해야 합니다.
songgj123 6년 전
일단 제 생각은 DP입니다.
cache[i][j][4]의 배열을 선언합니다.
배열의 의미는
좌표 (i, j)가 k번째로 저장됐을 때, 최대값입니다.
이게 성립한다고 생각한 이유는
i, j가 k번째로 더해져서 최대값이 되려면
주변 네 방향에서의 k-1번째 값 중에 최대값을 선택하면 되기 때문입니다.
그런데 이걸 직접 구현하니 칸을 반복해서 방문하는 경우가 생기더군요
일단 코드를 제외하더라도 제가 한 생각이 맞는지 궁금하네요
참고로
모든 모양을 배열로 저장해서 제출해보니 정답 나오네요....
혹시나 이게 진짜 풀이법은 아니겠죠??
다른 방식으로 푸신 분 댓글로 좀 알려주세요ㅜㅜ