URL https://programmers.co.kr/learn/courses/30/lessons/12913
문제 설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.
예를 들면,
1
2
3
4
5
| 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 이하의 자연수
문제 풀이
- 그냥 각 행에서 max값을 찾아 index로 저장하고 다음 행의 index를 0으로 변환하는 방식으로 진행했다.
- 테스트 문제는 풀긴했으나 모든 문제가 틀려서 무엇이 문제인지 확인해보니 추가한 test 케이스 2번이 20이 나와야하는것을 알수 있었다.
이유는 return 시키는 값이 max가 되어야하는데, 틀린 솔루션의 방식대로하면 1번째행에서 max값뽑고 2번째행에서 그 max값을 제외시키는것보다 1번째행에서 2번째 max값을 넣고 2번째 행에서 제일큰 max값을 넣을때 결국엔 제일 큰 값을 return 시킬수도 있어서다.
- 결국 모든 경우의 수를 생각해야 했고 제일 처음의 행을 제외한 모든 행에서 직전 행의 max값을 더하는 형태로 진행하였다
- 물론 직전 행의 max값 중에 같은 index를 가진 max값을 제외하고 더하게 하였다.
이후 가장 max값을 return하면됨
- 참조 : https://ssungkang.tistory.com/entry/%EB%95%85%EB%94%B0%EB%A8%B9%EA%B8%B0%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4level2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 틀린 솔루션
import numpy as np
def solution(land):
answer = 0
index = None
for i in range(len(land)):
answer += int(np.array(land[i]).max())
index = np.argmax(land[i])
if i + 1 < len(land):
land[i+1][index] = 0
else:
break
return answer
1
2
land = [[1,2,3,5],[5,6,7,8],[4,3,2,1]]
solution(land)
1
16
1
2
3
# 20이 나와야함
land = [[4, 3, 2, 1], [2, 2, 2, 1], [6, 6, 6, 4], [8, 7, 6, 5]]
solution(land)
1
19
1
2
3
4
5
6
7
8
9
def solution(land):
for i in range(len(land) - 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[i+1][0],land[i+1][1], land[i+1][2], land[i+1][3]))
1
2
land = [[1,2,3,5],[5,6,7,8],[4,3,2,1]]
solution(land)
1
16
1
2
land = [[4, 3, 2, 1], [2, 2, 2, 1], [6, 6, 6, 4], [8, 7, 6, 5]]
solution(land)
1
20