[Problem Solving] 땅따먹기

Sean·2023년 9월 29일

Problem Solving

목록 보기

90/130

문제

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

풀이

아이디어

맨 처음에는 그냥 열만 안 겹치게 해서 매 행마다 최대값을 선택해 나가면 되는 줄 알았다.
그런데 한 열에 알맞은 최대값이 여러 개인 경우가 문제였다.
반례) [[1, 1, 3, 1], [2, 3, 2, 2], [1, 4, 1, 1]], 9
내 아이디어로 했으면 3 + 3+ 1을 선택해서 7이 되는데, 사실 정답은 3 + 2+ 4 = 9인 것이다.
이런 케이스들을 모두 찾기 위해서 DFS를 사용해봤지만, 시간 초과가 났다.
그럼, 결국, DP라는 소리다.
- DP도 캐시 배열을 만들지 않고 가는 방법과,
- 캐시 배열을 만들어서 가는 방법

DFS (시간초과)

import sys
sys.setrecursionlimit(10 ** 6)

def solution(land):
    row = len(land)
    answer = 0
    
    def dfs(cur_sum, cur_col, depth):
        nonlocal answer
        if depth == row:
            answer = max(answer, cur_sum)
            return
        else:
            # print(depth, land[depth][cur_col], cur_sum)
            idxList = [i for i in range(4) if i != cur_col]
            for idx in idxList:
                dfs(cur_sum + land[depth][idx], idx, depth + 1)
    
    for i in range(4):
        dfs(land[0][i], i, 1)
    
    return answer

DP 코드 (캐시 배열 이용)

def solution(land):
    total_row = len(land)
    cache = [[0] * 4 for _ in range(len(land))]
    for i in range(4):
        cache[0][i] = land[0][i]
    
    #DP 시작
    for ridx in range(1, total_row):
        current_row = land[ridx]
        for i, score in enumerate(current_row):
            sliced = cache[ridx-1][:i] + cache[ridx-1][i+1:]
            cache[ridx][i] = max(sliced) + score

    return max(cache[-1])

DP 코드 (캐시 배열 없이)

이거는 주어진 배열 land에다가 계속 누적해서 가는 방법이다.

def solution(land):
	for i in range(1, len(land)):
    	for j in range(4):
        	land[i][j] += max(land[i-1][:j] + land[i-1][j+1:])

인사이트

이 문제는 모든 경우를 탐색해야 하지만, 시간효율적으로 탐색해야 하는 문제입니다. 또한, 이동할 수 있는 경로에 제약을 둠으로써, N+1의 위치에 왔을 때, 어디에서 N+1의 위치로 왔는지 추측할 수 있습니다.
그렇기 때문에 어떤 칸에 오는 데에 드는 비용을 기록해놓고, 다음 칸에 오는 데에 드는 비용을 위해서 활용한다면 시간효율적으로 문제를 풀 수 있습니다.
이런 느낌의 문제는 다음 문제와 같습니다.