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

Programmers - 43105. 정수 삼각형

접근1

Bottom-Up 방식 사용.

 

삼각형의 높이만큼 반복 돌리면서

리스트에 저장해나가며 밑으로 한 층씩 내려가면 될 듯?

맨 위를 1층이라고 하면

[[{1층-0번}], [{2층-0번}, {2층-1번}], [{3층-0번}, {3층-1번}, {3층-2번}]]

{n층-n번} 에는 그 지점까지 도달할 수 있는 모든 경우의 수를 집합(set)으로저장.

[[{7}], [{10}, {15}], [{18}, {16, 11}, {15}], [{20}, {25, 18, 23}, {19, 20, 15}, {19}]]

와 같은 느낌으로.

 

def solution(triangle):
    dp = [[set([triangle[0][0]])]]

    for F in range(1, len(triangle)):
        now = []

        # F층에서
        for i in range(len(triangle[F])):
            num = triangle[F][i]
            jset = set()
            # F-1 층의 내려올 수 있는 원소 2개
            # i=0일 때와 i=F일 때 예외처리 필요
            if i == 0:
                j1 = dp[F-1][i]
                jset.update(j1)
            elif i == F:
                j1 = dp[F-1][i-1]
                jset.update(j1)
            else:
                j1, j2 = dp[F-1][i-1], dp[F-1][i]
                jset.update(j1)
                jset.update(j2)

            now.append(set(map(lambda x: x+num, jset)))
        dp.append(now)

    # 3차원 리스트를 2차원 리스트로 병합.
    for F in range(len(dp)):
        newSet = set()
        for sets in dp[F]:
            newSet.update(sets)
        dp[F] = newSet

    return max(map(max, dp))

 

시간초과 나요...

 

접근2

Bottom-Up 방식으로 했으니까..

여기서 효율성을 개선시킬 수 있는 부분을 찾아보자..

if i == 0:
    j1 = dp[F-1][i]
    jset.update(j1)
elif i == F:
    j1 = dp[F-1][i-1]
    jset.update(j1)
else:
    j1, j2 = dp[F-1][i-1], dp[F-1][i]
    jset.update(j1)
    jset.update(j2)

    now.append(set(map(lambda x: x+num, jset)))

이 구간.. 그러니까

위층의 왼쪽 오른쪽에서 가능한 모든 경우의 수를 갖고와서 계산했는데

그냥 최댓값만 따와서 계산하면 되는 거잖아?

 

def solution(triangle):
    dp = [[triangle[0][0]]]

    for F in range(1, len(triangle)):
        now = []

        # F층에서
        for i in range(len(triangle[F])):
            num = triangle[F][i]
            num1, num2 = 0, 0
            # F-1 층의 내려올 수 있는 원소 2개
            # i=0일 때와 i=F일 때 예외처리 필요
            if i == 0:
                num1 = dp[F-1][i]
            elif i == F:
                num1 = dp[F-1][i-1]
            else:
                num1, num2 = dp[F-1][i-1], dp[F-1][i]

            now.append(max([num1, num2])+num)
        dp.append(now)

    return max(map(max, dp))

 

성공!