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

문제

접근법

잘못된 접근법

• 각 행에서 가장 큰 수를 찾는다. (이전 열과 동일한 열 제외하고)
• 가장 큰 수들을 더한다

잘못된 이유:
[[2, 3, 4, 5], [1, 1, 1, 1000]] 일때, 첫번 째 행부터 각 행을 검사해서 가장 큰 수를 더할 때,

5 + 1이 됨으로, 최댓값인 4 + 1000 이 되지 않는다.

풀이방법

1. 이전 행의 각 열들중 (현재 진행되는 열 제외) 가장 큰 값을 찾고 그 값과 현재 값을 더해서 현재 값에 저장을 해준다.

2. 그럼 다음 행을 검사할 때 또한 1번 과정을 반복한다. 이때 이전행은 다음과 같다
   이전 행 = 이전 행 + 이전 행의 이전 행에서의 최댓값 ⋯

3. 이렇게 하면, 둘째 행부터 각 열에 이전 행의 최댓값을 더해서 들어오기 때문에

4. 마지막 행에는 마지막 행의 각 열에서 진행된 각 열이 갖는 최댓 값을 갖을 수 있다.

5. 답은 마지막으로 진행된 행의 최댓값을 return 하면 된다

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

      return max(land[-1])

풀이방법2

이 풀이 방법은 내가 처음에 문제를 풀때, 생각하게 된 풀이 방법인데, 재귀적으로 풀었는데, 효율적이지 못한 풀이이다.

1. 재귀 함수로 쓸 함수의 매개변수로 찾고자하는 행, 열의 위치를 받는다.

2. 만약 찾고자하는 행이 마지막 행이면 그 값을 그대로 return 한다. land[row][col]

3. 정상적으로 진행 되었을때, 현재 찾고자 하는 값과, 다음 행에서 진행되는 열 을 각각 더한 값 중에서 최댓 값을 찾는다.

4. 그 최댓 값 찾고자 하는 행, 열 의 위치에 넣어주고 그것을 return 해준다

5. 이를 첫번째 행의 열들의 각각을 찾고 그 값중 최댓 값을 반환하면 답이 나온다.

import sys
# 효율성 통과를 위해서 재귀함수의 제한을 늘려줌
sys.setrecursionlimit(10**6)

def solution(land):
    visit = [[False for _ in range(len(land[0]))] for _ in range(len(land))]
    result = []
    def get_land(row, col, land):
        if row + 1 == len(land):
            visit[row ][col] = True
            return land[row][col]

        temp = 0
        for i in range(len(land[0])):
            if col != i:
                if visit[row + 1][i]:
                    temp = max(temp, land[row][col] + land[row + 1][i])
                else:
                    temp = max(temp, land[row][col] + get_land(row + 1, i, land))
                    visit[row + 1][i] = True
        land[row][col] = temp

        return land[row][col]

    for i in range(len(land[0])):
        result.append(get_land(0, i, land))


    return max(result)

생각할 점

현재에서 다음으로 갈때의 식을 찾기보다,

이전값이 정해져있을때, 현재 값을 어떻게 정하는지를 생각하는 것도 좋을 것 같다.