[프로그래머스 lv2] 땅따먹기(DP)

https://school.programmers.co.kr/learn/courses/30/lessons/12913#qna

프로그래머스

 

문제설명

 

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

 

예를 들면,

 

| 1 | 2 | 3 | 5 |

 

| 5 | 6 | 7 | 8 |

 

| 4 | 3 | 2 | 1 |

 

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

 

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

 

제한사항

  행의 개수 N : 100,000 이하의 자연수

  열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.

  점수 : 100 이하의 자연수

 

문제 해결 방법

 

DP를 활용하여 문제를 풀었음.

두번째 행 기준에서 첫번째 행에서 어느 열부터 출발하냐에 따라 두번째 행에서 시작하는 점수가 달라진다. 

첫번째 행에서 밟을 수 있는 모든 열을 기준으로, 두번째 행에서 밟을 수 있는 열을 밟아서, 두번째 행에서 시작할 수 있는 모든 점수 중 가장 큰 점수를 각 열에 기록했다. 그 다음 행도 이런식으로 점수를 기록한 후, 맨 마지막 행에서 최대 점수를 찾아서 리턴했다. 

 

 

코드 구현

 

DP로 구현한 코드

import copy
def solution(land):
    answer = 0
    
    lenL = len(land)
    originLand = copy.deepcopy(land)
    
    for j in range(0, lenL):
        if j + 1 == lenL:
            break
        
        for i in range(4):
            for k in range(4):
                if i !=k:
                    if land[j+1][k] < originLand[j+1][k] + land[j][i]:
                        land[j+1][k] = originLand[j+1][k] + land[j][i]
                    #print(land)
    answer = (max(land[-1]))
    

    return answer

 

 

DFS(재귀)로 구현후, 간단한 테스트케이스는 통과가 되지만, 제출시 시간초과와 런타임에러로 도배됐던 코드 

def solution(land):
    answer = 0

    check = [False] * 4
    
    #print(land[0])
    
    summ = 0
    maxValue = 0
    maxCnt = len(land)
    cnt = 0
    result = []
    def dfs(check, summ, cnt, result, rem):
        if cnt == maxCnt:
            
            result.append(summ)
            return
        originRem = rem
        for idx, i in enumerate(land[cnt]):
            #print(check, 'rem', rem)
            if check[idx] == True:
                continue
            elif check[idx] == False:
                summ +=i
                check = [False] * 4
                check[idx] = True
                cnt +=1
                # print('cnt',cnt, 'idx', idx, 'i', i, check, 'rem', rem)
                # print()
                rem = idx
                dfs(check, summ, cnt, result, rem)
                check[idx] = False
                check[originRem] = True
                rem = originRem
                summ -=i
                cnt -=1
    
    rem = 0
    for idx, i in enumerate(land[0]):
        summ += i
        check[idx] = True
        cnt +=1
        #print('cnt',cnt, 'i', i)
        rem = idx
        dfs(check, summ, cnt, result, rem)
        check[idx] = False
        summ -=i
        cnt -= 1
            
#     print(result)
#     print(max(result))
            
    answer = max(result)
    return answer

 

 

시간/공간 복잡도

 

 

최악의 경우 O(NlogN)

 

 

최적화 및 개선 / 어려웠던 점

 

내 기준에서 진짜 어려운 문제다. 역대급 어려웠다. 

DP문제는 직관적으로는 이해가 가는데, 코드 구현을 하려고 하니 너무 헷깔리는 부분이 많았다. 

 

그리고 처음부터 이 문제는 문제의 제한사항을 안보고(시간 복잡도를 고려하지 않고) 문제를 풀었었는데, 어떤 문제라도 시간 복잡도를 잘 고려하고 문제에 접근하는 것의 중요성을 아주 많이 느꼈다. 

 

아예 시간복잡도 별 알고리즘과 최대 연산 횟수를 포스트잇에 써서 컴퓨터 본체에 붙여놨다 

 

문제가 어렵긴한데 풀고나니 해방감이 아주 좋고, 즐거움이 느껴진다. 

 

그리고 다른사람이 이 문제에 대해서 상세히 풀이해준 글을 봤는데 처음에 글을 보고도 이해가 잘 안갔다. 

그림으로 그려보기도 했는데 이해가 잘 안갔다. 

 

다시 글을 이해하려고 했을때는 그림을 아주 상세하게 그려서 펼쳐놓고 고민을 많이 하고 해설을 읽어보고를 반복했는데, 

이해가 됐다. 

 

이해가 안되는 문제에 대해서 그림을 상세하게 그리는게 시간이 많이 들진 몰라도, 확실히 그림을 대충그리는 것보다 상세히 그리는게 도움이 많이 되는것 같다. 

 

그리고 내가 작성한 코드에 대해서 시간복잡도를 계산하는 방법을 다시 공부해야할 것 같은 느낌이 든다.