[Programmers] 프로그래머스 땅따먹기

문제. 프로그래머스 땅따먹기

---

문제 설명

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

 

출처 : 프로그래머스 땅따먹기

코딩테스트 연습 - 땅따먹기

---

나의 풀이 in Python3

#1 (실패)

#[Programmers] 프로그래머스 파이썬 > 땅따먹기
def solution(land):
    answer = max(land[0])
    idx = land[0].index(max(land[0]))
    orders = len(land)
    for o in range(1,orders):
        if idx != land[o].index(max(land[o])):
            answer += max(land[o])
            idx = land[o].index(max(land[o]))
        else:
            answer += max(land[o][:idx]+land[o][idx+1:])   
            idx = land[o].index(max(land[o][:idx]+land[o][idx-1:]))
    return answer

해당 문제는 그 전의 열과 겹치지 않는 선에서 각 행의 최대값을 더해 최고점을 만드는 게 핵심 포인트

 

첫번째 풀이의 경우 예시는 통과할 수 있었지만,

최종 제출 단계에서 계속 실패를 하여 어떤 게 잘못되었나 계속 생각해본 결과

각 행을 독립적으로 생각하여서 실패했다는 것을 깨달음.

 

예시

1 2 3 4

4 1 2 100

5 6 7 8

9 5 4 3

 

해당 예시로 코드가 실현될 경우

1. 첫 번째 행에서 가장 큰 값이 4이므로 채택
2. 2번째 행에서 4번째 열 선택 x -> 따라서 첫 번째 열에 있는 4를 선택함에 따라 100이라는 값을 놓침
3. 즉, 이렇게 독립적으로 시행될 때 최대의 값을 획득하는 데 실패

따라서, 각 행의 최대값들을 고려해야함 => n번째 행 값들에 n-1번째 행 값들의 최대값 더해주기

 

#2(성공)

#[Programmers] 프로그래머스 파이썬 > 땅따먹기
def solution(land):
    for i in range(1, len(land)):
        for j in range(len(land[0])): 
            #앞의 행에서 해당 열 제외 최대값 더하기 갱신
            land[i][j] += max(land[i-1][0:j] + land[i-1][j+1:])
    return max(land[-1])

 

알고리즘 풀이

1. i번째행, j번째 열에 그 전의 행인 i-1번째 행의 j번째 열이 겹치지 않는 선에서 최대값을 더해주기
2. 각 행들의 최대값을 고려하는 시행을 통해 마지막 행에서의 최대값 구하기

*포인트 : 문제를 풀 때, 하나의 예시에 빠지면 가장 중요한 조건을 놓칠 수가 있기에 여러 가지 예시를 도입하여 코딩하는 습관을 들이기!