Programmers] 정수삼각형

📌 파이썬으로 풀이

 

📌 문제 링크 :

프로그래머스

 

📌 문제 설명 :

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

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

 

 

📌 제한 사항

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

 

📌 입출력 예

---

추측) 

DP 알고리즘에 대한 영상을 보면서 이미 힌트를 봐버림 ㅠ

새로운 2차원 배열을 사용하여 반복되는 패턴에 따라 더한 값을 넣어 최종적으로 마지막 인덱스 배열에서 최대값을 출력하면 될 듯 하다. 반복될 작은 패턴 부분을 먼저 설명하자면 꼭대기 숫자를 그대로 새로운 트라이앵글 배열 같은 위치에 저장하고 다음 행의 왼쪽 숫자를 더해 새로운 트라이 앵글 배열에서의 왼쪽 숫자 위치에 저장, 오른쪽 숫자도 동일한 방식으로 저장하는 패턴이 돌아가게 하면 될 듯하다. 

겹치는 부분에 대해서는 더 큰 숫자가 남게 해서 더한 결과가 최대값들만 저장되게 하여, 이전 경우의 수 중 가능성이 없는 것은 먼저 배제하고 가장 높은 숫자가 될 수 있는 결과만을 가지고 패턴을 반복하는 방식으로 진행.

이렇게 함으로써 반복되는 식을 줄이고, 경우의 수를 줄이는 방식으로 하면 될거 같다. 

 

 

소스코드) 

* 1차) 실패 : 장렬한 올 런타임 에러

def solution(triangle):
    
    new_Triangle = [[0], [0, 0], [0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0, 0]]

    for idx in range(0, len(triangle)-1) :
        if idx == 0 :
            # 시작값은 바로 넣어주기
            new_Triangle[0] = triangle[0]

        for idx2, value2 in enumerate(triangle[idx]):
            #중간숫자
            first_Int = new_Triangle[idx][idx2]

            #왼쪽
            plus_Int1 = triangle[idx+1][idx2]
            sum1 = first_Int + plus_Int1
            if new_Triangle[idx+1][idx2] < sum1 :
                new_Triangle[idx+1][idx2] = sum1

            #오른쪽
            plus_Int2 = triangle[idx+1][idx2+1]
            sum2 = first_Int + plus_Int2
            if new_Triangle[idx+1][idx2+1] < sum2 :
                new_Triangle[idx + 1][idx2 + 1] = sum2
                
    # 마지막 결과중에서 가장 큰 값 리턴
    return max(new_Triangle[len(new_Triangle)-1])

* 2차) 바보다. 다양한 높이의 배열이 들어올건데 예시만 생각하고 배열을 하드코딩

def solution(triangle):
    
    # 더해준 값 넣어줄 다차원 배열 만들기
    new_Triangle = []
    for idx in range(0, len(triangle)) :
        list = []
        for idx2 in range(0, len(triangle[idx])) :
            list.append(0)
        new_Triangle.append(list)
        
    # 삼각에서 왼쪽값 오른쪽 값 더해서 다차원 배열에 넣어주기    
    for idx in range(0, len(triangle)-1) :
        if idx == 0 :
            # 시작값은 바로 넣어주기
            new_Triangle[0] = triangle[0]

        for idx2, value2 in enumerate(triangle[idx]):
            #중간숫자
            first_Int = new_Triangle[idx][idx2]

            #왼쪽
            plus_Int1 = triangle[idx+1][idx2]
            sum1 = first_Int + plus_Int1
            if new_Triangle[idx+1][idx2] < sum1 :
                new_Triangle[idx+1][idx2] = sum1

            #오른쪽
            plus_Int2 = triangle[idx+1][idx2+1]
            sum2 = first_Int + plus_Int2
            if new_Triangle[idx+1][idx2+1] < sum2 :
                new_Triangle[idx + 1][idx2 + 1] = sum2
                
    # 마지막 결과중에서 가장 큰 값 리턴
    return max(new_Triangle[len(new_Triangle)-1])

 

 

리뷰) 

먼저 힌트를 봐버렸지만 역시 직접 구현하는 것은 또 다른 이야기인 듯 하다. 뭔가 구현하고 보니까 이게 최선이 아닌거 같기도 ㅎㅎㅎ DP에 관련해서는 정말 다양한 방법이 많기 때문에 많은 문제를 풀어보면서 사고를 맞춰나가는 게 중요하다고 한다. 문제를 정말 다양하게 풀어봐야할 듯 하다.

 

 

 

---

참고 영상: