[프로그래머스] 땅따먹기 / 파이썬

문제 정리

---

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 이하의 자연수

입출력 예

land	answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

문제 풀이

---

처음엔 단순하게 for문으로 맨 위의 행의 최대값을 아래로 내려가면서 더하면 되는 간단한 문제구나 싶었습니다.
맨 위의 행부터 최대값을 구하고 다음 행에선 그 열을 제외한 최대값을 더해가는 형태로 구현했습니다.

def solution(land):
    answer = 0
    f_value = max(land[0])
    idx = land[0].index(f_value)
    answer += f_value
    for l in land[1:]:
        new_l = l[:idx] + l[idx+1:]
        value = max(new_l)
        idx = l.index(value)
        answer += value
    return answer

제출 결과 모든 테스트케이스를 실패했습니다.
질문하기의 반례를 참고해봤습니다.

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 100 |

| 4 | 3 | 2 | 1 |

위의 경우 최대 값은 3 + 100 + 4 = 107 이 나와야합니다.
그러나 위의 코드는 맨 위의 행부터 최대값을 구하고 다음 행에선 그 열을 제외한 최대값을 계산하기 때문에 5 + 7 + 4 = 16 이 나옵니다.
따라서 단순하게 맨 위의 행부터 계산하는 것이 아니라 가능한 경우의 수들을 구해야 하는 문제였습니다.

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

각 행의 최대값을 다음 행에 더해가며 마지막 행의 최대값을 반환하면 되겠다고 생각했습니다.

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

의 경우

| 1 | 2 | 3 | 5 |

| 10 | 11 | 12 | 11 |

| 4 | 3 | 2 | 1 |

여기서 8은 그 전 행의 최대값 5가 아닌 3이 더해지는 경우가 최대이기 때문에 11이 됩니다.

| 1 | 2 | 3 | 5 |

| 10 | 11 | 12 | 11 |

| 16 | 15 | 13 | 13 |

마지막 행의 최대값 16이 답이 됩니다.

최종 코드

---

def solution(land):
    n = len(land)-1
    for i in range(n):
        for j in range(len(land[0])):
            land[i+1][j] += max(land[i][:j] + land[i][j+1:])       
    return max(land[n])