[파이썬] 정수 삼각형

문제 설명

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

 

 

🎀 나의 풀이

# 시간 초과
def solution(triangle) :
    result=0        # 거쳐간 숫자의 최댓값
    row=len(triangle)       # 세로
    def dfs(depth, hap, idx) :
        nonlocal result
        if depth == row :
            result=max(result, hap)
            return
        for j in range(2) :
            dfs(depth+1, hap+triangle[depth][idx+j], idx+j)

    dfs(1, triangle[0][0], 0)
    return result

DFS

제출하니 시간 초과 뜨는 게 많다

시간 복잡도는 (N-1)*2*(N)

N-1을 한 이유는 꼭대기는 제외

대각선으로 2번 들어가니까 *2

N층에 N개의 요소

정리하면 O(N^2)

문제에서 입력이 최대 높이가 500인 삼각형이니 시간 초과가 뜰수밖에 😅

 

 

# 실패
def solution(triangle):
    answer = 0
    dp=0
    for i in range(0,len(triangle)-1,2) :
        m=max(triangle[i])	# 행에서 가장 큰 값
        dp+=m+max(triangle[i+1][i], triangle[i+1][i+1])
    return dp

 

다음 행으로 향하는 두 대각선 방향 중 더 큰 값을 더한다.

 

문제점 : 2열에서 8을 고르는게 최선인 것 같지만 3을 고르는게 최선임.

3열도 고려해야하네..

모든 경우의 수를 다 구해야하나..

 

# 실패
def solution(triangle):
    answer = 0
    for i in range(0, len(triangle)-1, 2) :
        dp=[]
        for idx, t in enumerate(triangle[i]) :
            dp.append(t+max(triangle[i+1][idx], triangle[i+1][idx+1]))
        answer+=max(dp)
    return answer

 

한 행에 있는 각각의 값들에 대해 계산하고 리스트 dp에 담았다.

dp에서 가장 큰 값을 answer에 더했다.

 위의 두가지 풀이 모두 알고리즘에 구멍이 있다ㅠ

당장 큰 값을 골라도 그 다음 행에 따라 또 달라지는데 이걸 커버 못했음.

 

 

✨ 다른 사람 풀이

 

# 출처 : https://codedrive.tistory.com/49
def solution(triangle):
    for i in range(1, len(triangle)) :
        for j in range(i+1) :
            if j == 0 :	# 왼쪽
                triangle[i][j]+=triangle[i-1][j]
            elif j == i:	# 오른쪽
                triangle[i][j] += triangle[i-1][j-1]
            else :	# 끼어있는 것들
                triangle[i][j]+=max(triangle[i-1][j], triangle[i-1][j-1])
    return max(triangle[-1])		# 마지막 행에서 가장 큰값

 

가장자리에 있는 값은 이전 가장자리 값을 더한다.

이전 행의 대각선 왼쪽, 오른쪽 중 큰 값을 더한다.

내가 구현했던 다음 행의 대각선 왼쪽, 오른쪽을 더한 방법과 다르다. 왜 방향을 다르게 해 볼 생각을 안 했을까?🤔

 

 

# 출처 : https://velog.io/@tjdud0123/%EC%A0%95%EC%88%98-%EC%82%BC%EA%B0%81%ED%98%95
def solution(triangle):
    triangle=[[0]+line+[0] for line in triangle]
    
    for i in range(1, len(triangle)) :
        for j in range(1, i+2) :	# 안쪽 열
            triangle[i][j]+=max(triangle[i-1][j-1], triangle[i-1][j])
    return max(triangle[-1])

 

모든 행의 가장자리를 0으로 만든다.

패딩을 넣어줘서 max(triangle[i-1][j-1], triangle[i-1][j])에서 인덱스 에러 예방

안쪽 열 값들만 계산한다.

 

 

 

 

문제 출처 💁‍♀️ 프로그래머스