[プログラマ]整数三角形(43105)

8815 ワード
programmers テキストリンク

質問リンク


https://programmers.co.kr/learn/courses/30/lessons/43105

質問する



ぶんかつ


  • アルゴリズム分類
    ダイナミックプランニング

  • 難易度
    プログラマレベル3

  • 言語の使用
    python 3

    • コード#コード#


    try 1


    フルナビゲーション


    すべての場合、
    ツリー構造を模倣した再帰呼び出しの使用を試みる
    def solution(triangle):
    answer = returnMax(triangle, 0, 0, 0)
    return answer


def returnMax(arr, indexY, indexX, sum):
    sum += arr[indexY][indexX]
    
    if(indexY == len(arr)-1): # 삼각형의 밑변인 경우 종료
        return sum
    
    # 삼각형의 그림 중 왼쪽 아래, 오른쪽 아래의 경로를 통했을 경우
    # 각각의 값들을 재귀호출로 탐색
    return max(returnMax(arr, indexY+1, indexX, sum),
               returnMax(arr, indexY+1, indexX+1, sum))

    結果


    問題の意図は正しいが,効率が低すぎる.

    敗者


    フルナビゲーションにはすべての場合の数値が含まれているため、大量の計算を繰り返す必要があります.
    また、DPに分類されていますが、コメントが行われていないことに気づき、最初からやり直します.

    try 2


    どうてきけいかくほう


    三角形の各層に沿って下へ行く.
    各ノードが許容できる最大値を保存するときに閉じるtriangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])部分的に示すように、ノードは上の2つのノードの大きな値に格納されます.
    def solution(triangle):
    answer = 0
    
    for i in range(1, len(triangle)): # 루트 제외
        for j in range(len(triangle[i])):
            if(j == 0):               # 왼쪽 끝
                triangle[i][j] += triangle[i-1][j]
            elif(j == len(triangle[i]) -1): # 오른쪽 끝
                triangle[i][j] += triangle[i-1][j-1]
            else:
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
                 
    answer = max(triangle[-1])
    return answer

    結果


    100点

    の最後の部分


    coteの練習はほとんどしていなかったので、かなりうろうろしていました.(実際には、予想外の試みが3回あります)
    また,コード構造はよく理解できない.これは後で補充しなければなりません.
    rman実験のアーカイブモードバックアップなし、正常なシャットダウンで現在のオンラインREDOログファイルのリカバリを失う
    15652:NとM(4)