정수 삼각형

백준 1932번: 정수 삼각형

아이디어

같은 크기의 배열을 만들어서 합을 기록한다. 이 때 본인과 더해질 수 있는 숫자는 왼쪽 위, 오른쪽 위 두 가지 경우 뿐이므로 둘 중 합이 더 커지는 경우를 기록한다. 맨 왼쪽, 맨 오른쪽은 선택의 여지가 없으므로 그냥 합한다.

코드

N = int(input())
t = []

for i in range(N):
    l = list(map(int, input().split()))
    t.append(l)

ans = [[] for _ in range(N)]
ans[0] = t[0]

for i in range(1, len(t)):
    for j in range(len(t[i])):
        # 양 끝의 경우
        if j == 0:
            ans[i].append(ans[i - 1][0] + t[i][j])
        elif j == i:
            ans[i].append(ans[i - 1][i - 1] + t[i][j])
        else:
            ans[i].append(max(ans[i - 1][j - 1], ans[i - 1][j]) + t[i][j])

print(max(ans[N - 1]))

여담

처음에 별 생각없이 완전탐색했다. 500! 인데 될 리가 없었다. 난 바보야.. 문제 카테고리 안 보고 푸는게 너무 어렵다.

def solve(h, i, ans):
    if h == N - 1:
        return ans
    return max(solve(h + 1, i, ans + t[h + 1][i]), solve(h + 1, i + 1, ans + t[h + 1][i + 1]))

print(solve(0, 0, t[0][0]))