[코테] 프로그래머스 파이썬 Lv2. 땅따먹기

땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요.

 

 

코딩테스트 연습 - 땅따먹기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

처음 시도는 각 행의 최대값을 구한 후에, 만약 같은 열에 해당하는 원소가 최대값이라면 이 열을 제외한 원소 중 최대값을 구해 더하는 방식으로 진행했다. 예제 코드에서는 성공했지만 시간이 오래 걸린다는 문제점이 있었다.

def solution(land):
    answer = 1
    dire=[]
    
    for i in land:
        # print(answer)
        if len(dire)==0:
            answer=max(i)
            dire.append(i.index(max(i)))
            continue
            
        check=max(i)
        
        if dire[-1] != i.index(check):
            dire.append(i.index(check))
            answer+=check
        else:
            if dire[-1] != 3:
                max1=max(i[:dire[-1]])
                max2=max(i[dire[-1]+1:])

                if max1>max2:
                    dire.append(i[:dire[-1]].index(max1))
                    answer+=max1
                else:
                    dire.append(i[dire[-1]+1:].index(max1)+dire[-1]+1)
                    answer+=max2
                    
            else:
                max1=max(i[:dire[-1]])  
                dire.append(i[:dire[-1]].index(max1))
                answer+=max1

    return answer

 

 

해결방법을 찾아보니, 가장 좋은 해결책을 취하는 Greedy 방식을 취하는 것이었다. 열의 개수는 고정되어 있기 때문에, 그 전의 열에 해당하지 않는 원소 중 최대값을 축적해가며 계산하여 풀이한다.

 

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