문제
https://programmers.co.kr/learn/courses/30/lessons/12913
풀이
문제에 제시된 조건을 읽자마자 각 행을 내림차순으로 정렬해서
이전 행에서 가져온 최대값과 열이 같으면 바로 다음 값을 찾는 식으로 구현했다.
def solution(land):
answer, preidx = 0, -1
land = [sorted(list(enumerate(x)), key=lambda x: x[1], reverse=True) for x in land]
for row in land:
print(row)
if row[0][0] == preidx : #가장 큰 값의 인덱스가 이전과 같을 경우
answer += row[1][1]
preidx = row[1][0]
else :
answer += row[0][1]
preidx = row[0][0]
print(preidx)
return answer
결과는 제시된 예시만 통과하고 전체 테스트케이스 실패.
조금씩 바꿔가며 시도해봤지만 계속해서 틀리길레
문제를 잘못 이해한건가 싶어서 질문 게시판을 살펴봤다.
max값을 담는게 항상 최대가 되진 않습니다.
[[1, 1, 99, 100], [1, 1, 1, 99]] 같은 경우
99, 99를 선택한 경우인 198이 최대가 되어야 합니다.
주재형―2020.08.13 13:18
주재형님, 감사합니다. DP로 접근하는 문제였다.
DP로 접근하는 문제인걸 인지하고 나니까, 열의 크기가 4로 고정된 이유가 이해 된다.
최대값을 4가지로 분할하여 각각 더해보자.
def solution(land):
for i in range(1, len(land)):
land[i][0] = max(land[i][0]+land[i-1][1], land[i][0]+land[i-1][2], land[i][0]+land[i-1][3])
land[i][1] = max(land[i][1]+land[i-1][0], land[i][1]+land[i-1][2], land[i][1]+land[i-1][3])
land[i][2] = max(land[i][2]+land[i-1][0], land[i][2]+land[i-1][1], land[i][2]+land[i-1][3])
land[i][3] = max(land[i][3]+land[i-1][0], land[i][3]+land[i-1][1], land[i][3]+land[i-1][2])
return max(land[i])
자신과 다른 열에 있는 값들과의 합 중 최대값을 자신이 갖는다.
이 동작을 모든 행에 걸쳐서 반복시키면 4개의 최대값이 나온다.
4개의 값 중 최대값이 문제에서 요구하는 최대값이 된다.
1시간을 넘게 고민한 문제인데 문제를 풀고 나서야
DP문제중에서도 가장 쉬운 축에 속한다는 걸 깨닫는다. 큰 일 났다.
댓글남기기