[프로그래머스 코딩테스트 연습] 땅따먹기 (Python3) Lv2

땅따먹기 게임 문제 풀이

문제 설명

땅따먹기 게임은 N행 4열로 이루어진 배열 형태의 땅을 가지고 진행됩니다. 게임의 규칙은 다음과 같습니다:

1. 각 행의 4개 숫자 중 하나를 선택하여 점수를 획득합니다.
2. 한 행씩 내려오며 점수를 얻어야 합니다.
3. 같은 열을 연속으로 선택할 수 없습니다.

예를 들어, 다음과 같은 배열이 주어졌을 때:

1 2 3 5
5 6 7 8
4 3 2 1

첫 번째 행에서 네 번째 칸(5)을 선택하고, 두 번째 행에서 두 번째 칸(6)을 선택하며, 세 번째 행에서 첫 번째 칸(4)을 선택하는 방식으로 진행됩니다. 이 때, 얻을 수 있는 점수의 최대값을 구하는 문제입니다.

제한사항

• 행의 개수 N: 100,000 이하의 자연수
• 열의 개수는 4개
• 점수: 100 이하의 자연수

문제 접근 방식

DP 방식 구현

1. DP 테이블 초기화:
   • 처음에는 land 자체를 DP 테이블로 사용합니다.
2. DP 테이블 갱신:
   • 각 행을 순회하면서 현재 칸에 이전 행에서의 최대값을 더하여 갱신합니다.
   • 단, 같은 열을 연속해서 선택할 수 없으므로 이전 행에서 현재 열을 제외한 나머지 열 중 최대값을 더합니다.
3. 최종 결과:
   • DP 테이블의 마지막 행에서 최대값을 선택합니다.

DP(동적 프로그래밍) 활용

DP 테이블을 활용하여 각 칸에서의 최대 점수를 저장해 나가며 해결합니다.
이전 행에서 현재 열을 제외한 나머지 열 중 최대값을 더해나가는 방식으로 구현합니다.

1. 문제 정의:
   • dp[i][j]는 i번째 행의 j번째 열을 선택했을 때 얻을 수 있는 최대 점수를 의미합니다.
2. 점화식 도출:
   • dp[i][j] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3]) + land[i][j] 단, 같은 열을 선택하지 않도록 제외하고 선택합니다.
3. 초기 조건 설정:
   • 첫 번째 행의 값은 그대로 dp 배열에 설정합니다.
4. 결과 도출:
   • 마지막 행의 최대 값을 구하여 반환합니다.

정답 코드

def solution(land):
    # DP 배열 초기화
    dp = land

    # DP 테이블 채우기
    for i in range(1, len(land)):
        for j in range(4):
            dp[i][j] += max(dp[i-1][:j] + dp[i-1][j+1:])

    # 마지막 행에서 최대값 반환
    return max(dp[len(dp)-1])

# 예제 입력
land = [
    [1, 2, 3, 5],
    [5, 6, 7, 8],
    [4, 3, 2, 1]
]

print(solution(land))  # 출력: 16

코드 설명

• dp = land: DP 테이블을 land로 초기화합니다.
• 이중 for문을 사용하여 각 행을 순회하며, 현재 칸에 이전 행의 최대값을 더합니다.
• dp[i-1][:j] + dp[i-1][j+1:]: 현재 열을 제외한 이전 행의 나머지 열 값들을 리스트로 만듭니다.
• max(dp[i-1][:j] + dp[i-1][j+1:]): 그 리스트 중 최대값을 구합니다.
• return max(dp[-1]): DP 테이블의 마지막 행에서 최대값을 반환합니다.

틀린 코드와의 비교

처음에 작성한 코드는 모든 행에서 최대 값을 선택하지만, 연속된 행에서 같은 열을 선택하지 않도록 하는 조건을 반영하지 못했습니다. 그 결과 최대값을 잘못 계산하게 됩니다.

# 처음에 틀린 코드
def solution(land):
    answer = 0
    for i in range(len(land)):
        print(land)
        answer += max(land[i])
        if i != len(land) - 1:
            land[i + 1][land[i].index(max(land[i]))] = -1
    return answer

이 코드는 다음과 같은 문제가 있습니다:

1. 현재 행에서 최대 값을 선택한 후, 다음 행에서 같은 열을 제외하는 방식으로 구현했지만, 이는 최적의 해답을 보장하지 않습니다.
2. 단순히 다음 행에서 같은 열을 -1로 설정하여 제외하는 방식은 여러 경우의 수를 고려하지 못합니다.

이와 달리, 정답 코드는 DP 배열을 활용하여 각 행의 선택 가능 값들을 종합적으로 고려하여 최적의 해답을 도출합니다.

요약

이 문제는 동적 프로그래밍을 활용하여 해결할 수 있으며, 각 행에서 선택할 수 있는 값들을 종합적으로 고려하여 최적의 해답을 도출합니다. DP 배열을 통해 이전 상태를 기억하고 이를 활용하여 다음 상태를 계산함으로써 효율적인 해결이 가능합니다.