문제 설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.
예를 들면,
| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.
제한사항
- 행의 개수 N : 100,000 이하의 자연수
- 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
- 점수 : 100 이하의 자연수
입출력 예
land answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]] 16입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
접근 방법
이번 문제를 처음 봤을 때에는 DFS를 통해 해결하려고 하였다. 그러나 시간초과가 발생하였고, 다이나믹 프로그래밍을 통해 해결해야 한다는 것을 알게 되었다. 이 문제의 점화식은 다음과 같이 구할 수 있었다.
DP[i][j]=max(DP[i-1])+land[i][j]
그러나 이 점화식만 사용한다면 같은 열에 접근하는 경우가 생기므로 예외 처리를 해야한다.
예외 처리를 위해 두번째로 작은 수의 x좌표를 반환하는 함수를 따로 작성하였고, 만약 max(DP[i-1])의 x좌표가 현재의 x좌표와 같을 경우에 작성한 함수를 사용하여 다른 x좌표를 취하도록 하였다. 이 경우의 점화식은 다음과 같다.
DP[i][j]=dp[i-1][get_second(i-1)]+land[i][j]
이 점화식을 사용하여 문제를 잘 해결하였다.
- 두번째로 큰 수의 x좌표를 반환하는 함수 get_second를 y를 인자로 갖도록 선언한다.
->land[0]의 길이만큼 반복하는 i에 대한 for문을 돌린다.
--> 만약dp[y][i]가 내림차순으로 정렬된dp[y][1]과 같을 경우, i를 반환한다. - dp를 0으로
land의 길이*land[0]의 길이만큼 채워 선언한다. land[0]의 길이만큼 반복하는 i에 대한 for문을 돌린다.
->dp[0][i]를land[0][i]로 갱신한다.- 1부터 land의 길이까지 반복하는 i에 대한 for문을 돌린다.
-> 임시변수 idx에dp[i-1]의 최댓값의 x좌표를 저장한다.
->land[0]의 길이만큼 반복하는 j에 대한 for문을 돌린다.
--> 만약 idx가 j와 같을 경우,
--->dp[i][j]를dp[i-1][get_second(i-1)]+land[i][j]로 갱신한다.
--> 그 외에는dp[i][j]를max(dp[i-1])+land[i][j]로 갱신한다. max(dp[len(land)-1]을 반환한다.
solution.py
def solution(land):
def get_second(y):
for i in range(len(land[0])):
if dp[y][i]==sorted(dp[y], reverse=True)[1]:
return i
dp=[[0]*len(land[0]) for _ in range(len(land))]
for i in range(len(land[0])):
dp[0][i]=land[0][i]
for i in range(1, len(land)):
idx=dp[i-1].index(max(dp[i-1]))
for j in range(len(land[0])):
if idx==j:
dp[i][j]=dp[i-1][get_second(i-1)]+land[i][j]
else:
dp[i][j]=max(dp[i-1])+land[i][j]
return max(dp[len(land)-1])
