[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/12913
📌문제 설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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 이하의 자연수입출력 예 )
💡 문제 풀이
처음 문제에 접근했을 때 이전에 풀었던 문제와 비슷하여 (기계적으로)단순히 재귀 + 완전탐색 방법으로 풀었는데 시간초과와 런타임에러 발생했다...
이후 좀처럼 해결하지 못하다가 손코딩을 통해 DP(Dynamic Programming)방법으로 풀어야함을 깨달았다.
깨달음 1) 손코딩의 중요성...
깨달음 2) 재귀를 이용하여 문제해결이 되지 않았다면 비효율적인 연산이 없었는지 확인하고 DP로 접근해야겠다.
step1) 반복문을 이용하여 land의 행을 순서대로 접근
step2) 연속하지 않는 열의 숫자를 더했을 때 최대값을 유지하며 진행
step3) 마지막 열까지 더했을 때 최대값이 정답!
손코딩으로 작성한 순서대로 단순하게 코딩을 짰을 때 아래와 같은 코드가 나왔다.
from copy import deepcopy
def solution(land):
candidates = deepcopy(land[0]) # 연산을 하며 실시간으로 최대값을 담는 리스트(0행을 초기값으로 선정)
for i in range(1, len(land)): # 1행부터 시작
step = deepcopy(candidates) # 연산을 위해 이전행까지의 최대값을 담는 리스트
for j in range(4): # 4개의 열을 반복
idx = 0 # j열과 연산할 index
while True:
if j == idx: # 만약 연속하는 열이면 idx+1로 다음단계 이동
idx += 1
continue
if idx == 4: # 4열 모두 탐색하였으면 break
break
candidates[idx] = max(candidates[idx], step[j] + land[i][idx])
idx += 1
return max(candidates)파이썬에서 리스트를 단순히 =를 통해 복사하면 얕은복사(shallow copy)가 이루어지기 때문에 deepcopy를 사용하였다.
문제를 풀고 정답을 제출하여 통과는 하였지만 "deepcopy를 굳이 사용할 필요가 있었을까..??" 하는 의문이들었다 🤨
생각해보니 주어진 리스트(land)를 탐색할 때 단계마다 최대값을 넣어서 계산하면 굳이 연산의 결과를 따로 저장하는 리스트가 필요없다.
def solution(land):
for i in range(1, len(land)):
land[i][0] = max(land[i-1][1], land[i-1][2], land[i-1][3]) + land[i][0]
land[i][1] = max(land[i-1][0], land[i-1][2], land[i-1][3]) + land[i][1]
land[i][2] = max(land[i-1][0], land[i-1][1], land[i-1][3]) + land[i][2]
land[i][3] = max(land[i-1][0], land[i-1][1], land[i-1][2]) + land[i][3]
return max(land[-1])특히, 문제는 단순히 4개의 열만 다루기 때문에 위처럼 간단하게 코드를 작성할 수도 있다.
실제로 첫 번째 코드의 실행속도보다 두 번째 코드의 실행속도가 3배가량 빨랐다.
알고리즘 문제를 풀 때 정답도 중요하지만 효율성도 깊게 고민해야겠다..!!😉
