[프로그래머스] #43105 정수 삼각형

문제

문제보기

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

풀이

동적계획법에 따른 규칙 탐색(Top-down 방식)

# 규칙 탐색
삼각형이 3줄 이상이면, 이런 방식으로 정답을 계산할 수 있다.
총합은 문제에서처럼 위에서부터 아래방향으로 계산해 나가는 것으로 하자.

마지막 줄과 마지막 바로 윗줄간의 관계를 탐색해본다.
1) 마지막 줄 바로 윗 줄의 각 원소들에 대하여, 해당 원소에 도달하기까지 총합들 중 최대값만을 취한다.
	- 즉, 바로 윗 줄 원소 하나하나에, 그 원소에 도달할 수 있는 총합들 중 최대값이 하나씩 부여되어있다.
	- 이를 그 줄의 '최대총합 리스트'라고 이해하자.
2) 마지막 줄 맨 처음(마지막) 원소는 무조건 모든 줄의 처음(마지막) 원소들의 합일 것이다.(모든 줄 공통)
3) 마지막 줄 나머지 원소들에 대해선 다음과 같은 계산과정을 거쳐 도출한다.
	- 마지막 줄 각 원소에 도달하기 위해선 반드시 바로 윗 줄의 인접한 두 원소 중 하나를 거쳐와야 한다.
	- 바로 윗줄의 인접한 두 원소의 '최대총합 리스트 원소'들중 더 큰 값을 취해 마지막 줄의 원소에 더해준다.	
4) 이렇게 도출된 마지막 줄까지의 총합값들을 계산하여 나열한 뒤, 이 중 최대값을 취하여 반환한다.

이런 방식으로 한 줄씩 '최대총합 리스트'를 구성해나가면 몇줄짜리이던 정답을 도출할 수 있다.

# 초기값 설정
삼각형이 1줄짜리이면 단 하나의 값이 곧 정답이다. 
삼각형이 2줄짜리이면, 2번째 줄의 값 중 최대값과 맨 처음 값의 합이 곧 정답이다.

코드

def solution(triangle):
    if len(triangle) == 1: # 1층 삼각형인 경우
        return triangle[0][0]
    elif len(triangle) == 2: # 2층
        return max(triangle[1]) + triangle[0][0]
    else: # 3층 이상
        res = [] # 각 줄의 최대총합 리스트들을 담을 리스트(Memoization)
        res.append(triangle[0]) # 첫 줄의 최대총합 리스트(=그냥 해당 값)
        res.append([triangle[1][0] + triangle[0][0], triangle[1][1]+triangle[0][0]]) 
        # 두번째 줄 최대총합 리스트
        
        # 세번째 줄 이상에서의 규칙 구현
        for i in range(2, len(triangle)):
            list = [] # (i+1)번째 줄의 최대총합 리스트
            list.append(res[i-1][0] + triangle[i][0]) # 처음 값 = 맨 처음값들의 합
            for j in range(1, len(triangle[i])-1):
                # 위의 인접한 두 원소 중 더 큰 최대총합 값을 더해준다.
                list.append(max(res[i-1][j-1], res[i-1][j])+triangle[i][j])
            list.append(res[i-1][-1] + triangle[i][-1]) # 마지막 값 = 맨 마지막값들의 합 
            res.append(list) # 전체 최대총합 리스트 목록에 추가

    return max(res[-1]) # 최대총합 리스트들 중 마지막 리스트의 최대값을 반환하면 정답

개선된 코드

def solution(triangle):
    for t in range(1, len(triangle)):
        for i in range(t+1):
            if i == 0:
                triangle[t][0] += triangle[t-1][0] # 맨 처음 값
            elif i == t:
                triangle[t][-1] += triangle[t-1][-1] # 맨 마지막 값
            else:
                triangle[t][i] += max(triangle[t-1][i-1], triangle[t-1][i]) # 나머지 값
    return max(triangle[-1])

• 굳이 초기값을 따로 설정해 줄 필요가 없다. 위 코드는 삼각형이 1줄짜리여도 작동한다.
  • 새로 깨달은 점: 반복문을 for i in range(1, 1)로 잡아서 해당하는 i가 없어도 error가 안난다.
  • 따라서, 삼각형이 1줄짜리여도 error없이 마지막 줄의 반환문을 실행할 수 있다.
• 굳이 최대총합 리스트를 담을 리스트를 별도로 선언할 필요가 없다.
  • 위 코드에선 그냥 기존의 triangle의 해당 원소값을 최대총합으로 치환해버려 메모리를 절약한다.
  • 어차피 해당 원소 위치에 그대로 값을 대체하고, 다음 줄을 계산할때는 치환된 값만 사용되기 때문이다.

나가며

규칙탐색까진 좋았으나, 이를 효율적인 코드로 구현해내지 못해 아쉬웠다.

아래의 개선된 풀이는 타인의 풀이인데, 아이디어는 완전히 나의 아이디어와 동일했기 때문에 더욱 그렇다.

조금 더 수련이 필요하다.