[ 2023-04-13 🧤TIL ]

백준 1932번

import sys

input = sys.stdin.readline

n = int(input())
n_tree = []

for _ in range(n):
    leaf = list(map(int, input().split()))
    n_tree.append(leaf)

# 깊이가 증가할 때 마다 깊이 값만큼의 배열크기가 지정된다.
dp = [[0 for _ in range(i)] for i in range(1, n+1)]
dp[0][0] = n_tree[0][0]  # 첫 번째 요소 넣어서 시작

for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            dp[i][j] = dp[i-1][0] + n_tree[i][0]
        elif j == i:
            dp[i][j] = dp[i-1][j-1] + n_tree[i][j]
		#dpeth의 첫 값과 끝 값은 이전 depth의 동일 인덱스 값을 더한 값이 들어간다.(비교할 필요 없음)
        else:
        	# 비교 대상이 필요한 경우
            # 이전 depth의 2개의 값과 비교하여 큰 값 넣기
            com1 = dp[i-1][j-1] + n_tree[i][j]
            com2 = dp[i-1][j] + n_tree[i][j]
            if com1 > com2:
                dp[i][j] = com1
            else:
                dp[i][j] = com2
print(max(dp[n-1]))

처음에 풀었던 방법이 잘못되었다는 것을 깨닫고..
어떻게 풀어야는지 풀이를 찾아보고 다시 풀어보았습니다.

위에 문제에서 중요한 부분은 dp[0][0] = n_tree[0][0]를 넣었을 경우, for i in range(1,n)로 시작해야 한다는 것입니다.
안넣었을 경우에는for i in range(n) 시작해야 합니다.

하지만 제 생각에는 dp[0][0]의 값은 기본적으로 다 알고 있으니.. 가독성을 위해 넣어주게 좋을 것같다는 생각이듭니다. 물론 저의 생각임 반복 횟수도 줄어드니 기능 상에도 좋고..

틀린 코드 공개😗

import sys

input = sys.stdin.readline

n = int(input())
n_tree = []

for _ in range(n):
    leaf = list(map(int, input().split()))
    n_tree.append(leaf)

dp = [[0 for _ in range(2**i)] for i in range(1, n+1)] 
# 메모리초과 여기서 발생하는 듯..
dp[0][0] = n_tree[0][0]

for i in range(1, n):
    index = 0
    for j in range(len(n_tree[i])-1):
        dp[i][index] = n_tree[i][j] + dp[i-1][j]
        dp[i][index+1] = n_tree[i][j+1] + dp[i-1][j]
        index += 2

print(max(dp[n-1]))

depth가 증가할 때 마다 2 ^ depth만큼의 계산이 발생하는 것을 구현하려 했지만...ㅎㅎ 망함 😂