땅 따먹기
문제 설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.
시각화
아래와 같이 한 줄씩 3개 주어졌을 때 최대 값을 구해보자.
파란색 땅을 밟으면 5 + 7 + 4 = 16 이 된다.
문제 해결 과정
중요한 조건은 밟은 땅 바로 아래는 밟지 못한다는 것이다.
최대 값을 구하는 방법은 단순하게 각 줄에서 가장 큰 값들을 계산하면 된다.
각 줄에서 가장 큰 값 2개를 선택한다.
가장 큰 값을 바로 밑에를 제외하고 더한다.
2번째로 큰 값은 1번째로 큰 값 밑에 더한다.
다시 두 번 째 줄에서 가장 큰 값, 두 번째로 큰 값을 선택한다.
가장 큰 값을 바로 밑에를 제외하고 더한다.
두 번째로 큰 값은 1번째로 큰 값 밑에 더한다.
마지막 줄일 경우에는 가장 큰 값을 반환하면 된다.
전체 코드
한 줄 씩 내려가며 최대 값들을 설정해주면 된다.
def solution(land):
for y in range(0, len(land) - 1):
row = land[y]
order_row = sorted(row)[::]
max_1, max_2 = order_row[-1], order_row[-2]
max_1_i, max_2_i = row.index(max_1), row.index(max_2)
indexes = [0, 1, 2, 3]
indexes.remove(max_1_i)
for index in indexes:
land[y + 1][index] += max_1
land[y + 1][max_1_i] += max_2
return max(land[-1])
