문제 설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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 |
접근
처음에 보고 그리디라고 생각했다. 맨 처음에 가장 높은 점수가 있는 칸을 고르고 이후 내려갈 수 있는 칸 중 가장 높은 점수를 지닌 칸으로 내려가다보면 정답을 구할 수 있을 것이라 생각했다.
다만, 이 접근법은 같은 점수라면 그 다음 행까지 고려해야 한다는 특징이 있었다. 같은 점수가 여러 개라면 그 중 어디가 최적인지 고려해야 하는데 그를 고려할 수 있는게 바로 다음 행이기 때문이다.
다른 사람의 해설
[프로그래머스] 땅따먹기 / 파이썬 - TEAM EDA
위 글에 적힌 해설을 보고 나니 내 방식이 완전히 잘못된 접근은 아니었다.
다른 사람의 풀이를 보면 볼수록 내 머리는 굳은게 아닐까라는 생각이 든다. 접근법을 어떻게 저렇게 잘 찾아낼 수 있는걸까. 나는 이 방법 막히고 어떻게 해 볼 생각도 안 들었는데......
그렇게 만들어낸 풀이
def solution(land):
row = len(land)
for i in range(1, row):
land[i][0] += max(land[i - 1][1:])
land[i][1] += max(land[i - 1][0], land[i - 1][2], land[i - 1][3])
land[i][2] += max(land[i - 1][0], land[i - 1][1], land[i - 1][3])
land[i][3] += max(land[i - 1][:3])
return max(land[-1])이전 행에서 자신의 열을 제외한 나머지 중 가장 큰 값을 행의 모든 요소에 더한다. 이렇게 하면 행을 내려오면서 점수를 얻게 되는 기능을 구현한 것이다.
이렇게 하면 각 출발 땅에 따라 얻을 수 있는 최적의 점수가 기록되어 있다. 여기서 가장 큰 값을 반환하면 문제에서 요구하는 정답을 구할 수 있다.
다른 사람의 풀이
def solution(land):
for i in range(1, len(land)):
for j in range(len(land[0])):
land[i][j] = max(land[i -1][: j] + land[i - 1][j + 1:]) + land[i][j]
return max(land[-1])문제에서 각 행에 들어있는 요소의 수는 4개라고 단정을 지었기 때문에 위와 같이 나열하는 식으로 구현할 수 있었다.
그것을 이중 for문으로 위와 같이 구현할 수 있다.
