[프로그래머스] 땅따먹기 문제

Lv2문제입니다😉

---

<문제 설명>

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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

---

내가 생각한 풀이

한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙을 유의하며

한행씩 방문하며 answer이라는 행렬에 값을 더해가고

이전에 방문했던 열을 제외한 열에서의 최대값을 다음에 밟도록 해야겠다고 생각했습니다.

 

그렇게 나왔던 첫 답안

 

코드(수정 전)

def solution(land):
    answer = []
    for line_num in range(len(land)):
        if not answer:
            answer = land[line_num]
        else:
            answer[0] = answer[0]+max(land[line_num][1:])
            answer[1] = answer[1]+max(land[line_num][0:1]+land[line_num][2:])
            answer[2] = answer[2]+max(land[line_num][0:2]+land[line_num][3:])
            answer[3] = answer[3]+max(land[line_num][:-1])
    return max(answer)

그러나 이렇게 코드를 진행하게 되면 위의 예시인

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 | 입력을 적용했을 때

answer에 값이

 | [1, 2, 3, 5]

 | [9, 10, 11, 12]
↓[12, 14, 15, 16] 이렇게 더해지며

해당 입력에는 우연하게 정답일뿐 잘못된 코드이다.

최종적으로 이전에 어떤값을 더해왔는지와 무관하게 결과적으로 최대값만 출력해내면 되는 문제의 의도와 달라진다.

 

수정 된 코드

def solution2(land):
    for i in range(len(land)-1):
        land[i+1][0] = max(land[i][1:]) + land[i+1][0]
        land[i+1][1] = max(land[i][0:1]+land[i][2:]) + land[i+1][1]
        land[i+1][2] = max(land[i][0:2]+land[i][3:]) + land[i+1][2]
        land[i+1][3] = max(land[i][:-1]) + land[i+1][3]
    return max(land[-1])

동일하게 입력된 land에서

[10, 11, 12, 11] 
[16, 15, 13, 13] 이렇게 출력하고 정답 16을 출력한다.

 

처음에 이해가 잘안갔는데 동작 과정을 보고 이해했다.

 

(1열 예시, 동일한 열 제외 5+2 or 3, 5 -> 10이 가장 큰 경우) 

| 1 | 2 | 3 | 5 | ↑ 

| 5 | 6 | 7 | 8 |  |  | 10 | 11 | 12 | 11 |

| 4 | 3 | 2 | 1 |     | 4 | 3 | 2 | 1 |

 

현재 행의 이전 방문이라고 볼 수 있는 경우(동일 열 제외) 중

가장 최대값이 되게하는 열의 값을 선택해 더해간다고 생각하면 된다.

그리고 위의 코드대로하면 불필요하게 answer이라는 변수를 만들 필요도 없다.

land의 가장 끝 값이 곧 최대 값이 되는 각 열의 경우이고 이중 최대값을 출력하면 된다.

 

문제출처: https://programmers.co.kr/learn/courses/30/lessons/12913

코딩테스트 연습 - 땅따먹기 | 프로그래머스

---

휴우,, dp활용 문제인데

dynamic programming에 대한 이해가 부족해서인지

쉽지 않았습니다 ㅇㅅㅇ

dp자체에 대한 이론정리가 필요할거같습니다...