땅따먹기(프로그래머스-level2)

안녕하세요 여러분

알고리즘 외에도 여러가지를 공부하다보니 하루에 한 개씩 포스팅을 하겠다던 계획을 지키기가 많이 어렵네요 ㅠㅠ

곧 알고리즘 외에도 웹프로그래밍, 인공지능 등 유익한 정보로 찾아뵙도록 하겠습니다.

오늘 알아볼 내용은 '땅따먹기' 입니다.

제목만으로는 무슨 문제가 유추가 안될텐데요, 

문제는 다음과 같습니다.

[ 문제 ]

땅따먹기 게임을 하려고 합니다.

땅따먹기 게임의 땅(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 이하의 자연수

입출력 예

land    [[1,2,3,5],[5,6,7,8],[4,3,2,1]]

answer 16

2단계라 그런지 큰 어려움 없이 코드를 써내려갔습니다. 

[ 잘못된 풀이 ]

def solution(land):
 
    answer = 0
 
    N = len(land)  # N은 행의 개수가 된다.
 
    num = 5  # 첫 행에서는 num 이 영향을 미치면 안되므로 열의 총 수인 4보다 큰 5를 대입해놓았다.
 
    for i in range(0, N):  # 0번째 행부터 N-1행까지 반복
 
        max = 0
 
        for j in range(0, 4):  # 각 행의 열들을 반복
 
            if num == j:  # 바로 직전의 행과 같은 열을 밟을 수 없다.
 
                continue
 
            if land[i][j] > land[i][max]:
 
                max = j  # 각 열에서 최대값을 찾기
 
        answer += land[i][max] #최대값들 더해주기
 
        num = max # 이번 행에서 최대였던 열을 저장하여 다음 행에 영향을 준다.
 
    return answer

각 코드에 대한 설명은 옆에 주석으로 적어두었으니 전체적인 풀이방법은

첫번째 행부터 탐색을 하며 가장 큰 수를 고르고,

그 다음 행으로 내려와서 바로 직전 행의 최대값과 같은 열에 있는 수를 제외한 최대값을 고르는 과정을 반복했습니다.

그 결과,

주어진 예시에서는 맞았지만, 

전체에서는 보기 좋게 틀리고 말았습니다.

 

그래서 다른 예를 생각하다보니 너무 말도 안되는 실수를 했더라고요.

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 100 |

| 4 | 3 | 2 | 1 |

다음과 같은 상황을 생각해볼까요?

당연히 100이 압도적으로 크니까 100을 고르는 경우가 문제에서 원하는 retrun 값이 될 겁니다.

하지만 제 코드대로 수를 고르다보면

첫번째에서 가장 큰 수인 5를 고르고 두번째에서 가장 큰 수인 100를 못고르게 됩니다. 

당연히 최대값을 return 하지 못하는 문제가 발생하고 말죠..

결국에는 모든 상황을 다 고려해줘야하는데 그러기 위해서는 시간복잡도가 너무 커집니다.

그래서 생각해낸 방법은 아래 코드와 같습니다.

def solution2(land):
 
    answer = 0
 
    N = len(land) # N은 행의 개수가 된다.
 
    for i in range(0,N-1):
 
        land[i+1][0] += max(land[i][1],land[i][2],land[i][3])
    # i+1번째 행에 0번째 열에는 i번째 행에 1,2,3 열 중 최대값을 더해준다. 이런식으로 계속 더해나가면
    # N-1번째에 열들을 각 선택지에서 가질 수 있는 최대값이 된다.
 
       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])
   
    answer = max(land[N-1])  # 바로 위에 코드가 똑같은 코드다. N-1행에서의 최대값을 가지는 열 answer에 대입한다.
    # answer = max(land[N-1][0],land[N-1][1],land[N-1][2],land[N-1][3]) 

    return answer

어떤 식으로 접근했는지 설명을 드리면

n번째 행에 값들에 n-1번째 행들의 값들의 최대값을 더해줘 쌓여가는 방식입니다.

물론 같은 열에 있는 값은 제외하고 말이죠.

이렇게 설명하면 어려울 수도 있으니 주어진 예시를 통해 과정을 살펴보도록 할께요.

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

먼저 5,6,7,8이 있는 두번째 행에 첫번째 행의 수들의 최대값을 더할 겁니다.

5,6,7에는 첫번째 행의 최대값인 5가 더해질테지만 8에는 같은 열에 있는 5를 제외한 최대값 3이 더해지겠죠.

그 결과,

| 10 | 11 | 12 | 11 |

| 4 | 3 | 2 | 1 |

다음과 같이 될 껍니다. 마찬가지로 3번째 행에도 더해주면,

4,3,1 에는 전 행의 최대값인 12가 2에는 12를 제외한 최대값 11이 더해질 겁니다. 

그 결과,

| 16 | 15 | 13 | 13 |

다음과 같은 값을 가지게 되고

여기서 최대값인 16이 return 이 됩니다.

이런 식으로 계산할 경우 모든 경우를 빠짐없이 고려해줄 수 있습니다.

마무리

level 2 라고 해서 큰 고민없이 접근했었는데 방심하다가 큰 코 다쳤습니다.

이 문제도 처음부터 여러 가지 예시들을 고려하고 코드짜기 시작했으면 안해도 되었을 실수죠.

또 이렇게 자기반성을 마치도록 하겠습니다.

항상 겸손한 자세로..!