문제
주어진 land는 N행 4열이고, 1행에서 시작하여 아래 행으로 내려가면서 같은 열 이외의 열에 있는 숫자를 추가해나갈 수 있다. 마지막 행까지 왔을 때, 최댓값을 구하면 된다.
그렇다. 예를 들어
| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
로 land가 주어지면 1열에서는 이후 2열의 6,7,8 중 가장 큰 8을 선택하고 3열에서 4,3,2 중 가장 큰 4를 선택하여 1+8+4 = 13 이 1열의 최댓값이 된다.
마찬가지로 2,3,4 열이 만들어낼 수 있는 각각의 최댓값을 구해서 마지막 행에서 가장 큰 값을 answer로 출력하면 된다.
어떻게?
단순하게 먼저 생각해보자. 먼저 1행에서 1열을 선택했을 때의 최댓값을 구하고, 같은 방식으로 2,3,4열을 구해서 그 중 최댓값을 구하면 된다. 예시를 사용하면 1행 1열의 1이 선택되고, 2행에서 1열을 제외한 최댓값 8을 선택하고, 3행에서 4열을 제외한 최댓값 4를 선택한다.
def solution(land):
answer = 0
ans = []
for i in range(4):
col = i
result = 0
for j,row in enumerate(land):
if j == 0:
result += row[col]
print(result)
else:
sp = row[:col] + row[col+1:]
print(sp)
maxNum = max(sp)
result += maxNum
col = row.index(maxNum)
ans.append(result)
print(ans)
print(ans)
answer = max(ans)
return answer이 코드는 샘플케이스는 통과하는데..왜 안될까?
뭐가 문젠지 모르겠다.
이번에는 DP를 이용한 코드다. DP가 뭔가?
나무위키에서는 이렇게 말한다..
어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘을 총칭한다
여기에서 눈여겨 보아야 할 점은 '과거에 구한 해를 활용' 인 것 같다.
'기억하며 풀기' 라는 말로 더 적절하게 해석 될 수 있을 것 같다.
그럼 이 문제에서는 무엇을 기억하며 푸는걸까?
1행에서의 최댓값을 기억한다.
1행의 기억된 값들을 가져와서 2행에서의 (각 열의) 최댓값구하고 기억한다.
3행에서도 1~2행을 따로 구하는게 아니라, 기억되어 있는 2행까지의 최댓값에 각 열의 조건에 맞는 최댓값들을 더해준다.
...
마지막 행까지 반복한다.
메모이제이션과 비슷한 개념이라 볼 수 있겠다. 사실 메모이제이션도 DP의 한 종류라 한다.
코드로 보는게 덜헷갈리고 이해가 더 빠르다.
코드
def solution(land):
answer = 0
map = []
for i in land:
map.append(i)
for i,v in enumerate(map):
if i==0:
continue
x = max(map[i-1][1], map[i-1][2], map[i-1][3])
map[i][0] += x
x = max(map[i-1][0], map[i-1][2], map[i-1][3])
map[i][1] += x
x = max(map[i-1][0], map[i-1][1], map[i-1][3])
map[i][2] += x
x = max(map[i-1][0], map[i-1][1], map[i-1][2])
map[i][3] += x
# print(map)
answer = max(map[i])
return answer