프로그래머스 땅따먹기 c++ 풀이
문제 정리
- 땅따먹기의 땅은 총 N행 4열
- 모든 칸에는 점수가 있다.
- 1행부터 땅을 밟으며 한 행씩 내려오며, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 한다.
- 단, 한 행씩 내려올 떄, 같은 열을 연속해서 밟을 수 없다.
- 마지막 행 까지 내려왔을 때, 얻을 수 있는 점수의 최대값으 구하여라.
문제 접근
DP??? 백준의 진우의 달 여행(Large) 문제와 비슷한 방식이라고 생각했습니다.
우선 dfs로 풀어보았습니다. 효율성 테스트도 있어서 시간초과 발생!!!
그래서 이번에는 풀이를 머릿속에 넣고 dp로 접근했습니다.
풀이가 잘 기억이 나지 않아 달 여행 문제 풀이를 보고 손으로 정리해보았습니다.
3차원 배열을 만들어서 [이전 col][현재row][현재col] 이렇게 해서 최대 값을 갱신해 나간다면 풀 수 있을것이라 생각했습니다.
문제 풀이
- 처음 초기화를 진행합니다. 맨 위 0행은 이전에 다른 곳에서 오는 것이 아니므로 land 값 그대로 갖습니다.
- 4중 for문을 돌며 dp 배열을 갱신해나갑니다.
- i는 현재 행, j는 현재 이전 열, k는 현재 열, q는 두 번 이전의 열을 나타냅니다. 즉 다음과 같습니다.
(i-2, q) -> (i-1, j) -> (i, k)
i,k 점에서의 최대 값은 이전 행의 최댓 값에 현재 k열의 land값을 더한 값 중에서 최댓 값을 찾으면 됩니다.
max(dp[j][i][k], dp[q][i-1][j] + land[i][k])
- dp[q][i-1][j] : 이전 (i-1, j) 까지의 점수 최댓값. 이는 (i-2, q) -> (i-1,, j)로 왔음을 나타냅니다.
- land[i][k]: (i,k)에서의 점수
- dp[j][i][k]: (i,k) 까지의 점수 최댓값. 이는 (i-1, j) -> (i, k)를 나타냅니다.
이때 연속해서 같은 열을 반복할 수 없으므로 q와 j가 다르고, j와 k도 달라야 합니다.
- 그리고 마지막 행에서 최댓 값을 찾으면 됩니다. 이는 마지막 행의 어느열에 도착하는게 가장 높은 점수를 얻는지 찾는다는 의미와 같습니다.
프로그래머스 level2 땅따머기 c++ 코드