[프로그래머스] 땅따먹기 (Python) - DP
문제 설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.
예를 들면,
로 땅이 주어졌다면, 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
문제의 예시와 같습니다.
def solution(land):
max_list = [x for x in land[0]] # 1*4 배열로, 해당 경로까지의 최댓값을 저장
for row in range(1,len(land)):
#행을 읽어들이면서
#1) max_list에서 같은 인덱스를 제외하고 가장 max 값이 무엇인지 알아내기
#2) 해당 max 값은 현재 행의 해당 값과 더해져서 max_list에 저장됨
max_list = [col + max(max_list[:i] + max_list[i+1:]) for i, col in enumerate(land[row])]
return max(max_list)리팩토링 하느라 죽는 줄 알았다 ... 사실 풀기도 어려웠음
자꾸만 max_list의 값을 갱신했더니 계속 max_list의 max 값을 불러올 때 갱신된 값을 불러와버리는 상황 발생...
그래서 deepcopy 사용했더니 코드가 너무 더러워져버리고
효율성에서 굉장히 많은 시간이 걸린 후에 통과하길래 (통과는 했지만 8초정도 걸리는 상황..)
고치기로 맘먹고 고쳤다. 성공해서 다행이다...
한가지 배운점은, 나는 아직 DP를 잘 모른다는 것
ㅋㅋㅋㅋㅋ
이렇게 풀어야지 하는 생각은 문제를 보자마자 알 수 있었는데 그것을 구현하기까지 정말 많은 시간이 걸렸다.
바보.... 디피를 공부하자!