[프로그래머스] [Level 2] [다이나믹 프로그래밍] 땅따먹기

땅따먹기

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

 

• 내 풀이
  • 테스트 코드는 pass
  • 제출: 실패, 런타임에러
    • 한 행에 같은 값이 나올 경우 고려하지 못함
  • → Hint) 다이나믹 프로그래밍 방식으로 풀어야함

def solution(land):
    ex1=[]
    ex2=[]
    result=0
    idx0,idx1,idx2=0,0,0
    count=0
    for i in range(len(land)-1):
        m1=max(land[i])
        idx1=land[i].index(m1)
        if i>0 and idx0==idx1:
            m1=ex2[1]
            idx1=land[i].index(m1)
        m2=max(land[i+1])
        idx2=land[i+1].index(m2)
        
        #정렬할 복사본
        ex1=sorted(land[i],reverse=True)
        ex2=sorted(land[i+1],reverse=True)
        
        if idx1==idx2:
            count+=1
            if m1+ex2[1]>=m2+ex1[count]:
                result+=m1
                if i+1==len(land):
                    result+=ex2[1]   
            else:
                result+=ex1[count]
                idx0=land[i].index(ex1[count])
                if i+1==len(land)-1:
                    result+=m2
                continue
        else:
            count=0
            result+=m1
            if i+1==len(land)-1:
                result+=m2
        idx0=idx1
                
    return result

#성공 테스트케이스
land=[[1, 2, 3, 5], [5, 6, 7, 8], [4, 3, 7, 1]]
print(solution(land))
#결과
18

#실패 테스트케이스
land=[[1, 1, 1, 1], [2, 2, 2, 3], [3, 3, 3, 6], [4, 4, 4, 7]]
print(solution(land))
#결과 
9 #정답: 14

 

• 다른 사람 풀이
  • 다이나믹 프로그래밍
  • 이전 행에서 선택한 열(a)을 제외한 리스트에서 최댓값을 뽑아 더함
  • a 이전 열 리스트 + a 이후 열 리스트 = a열만 제외한 리스트

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:])

    return max(land[len(land)-1])