백준 1932 - 정규삼각형 [SILVER 1]

N의 높이를 가진 삼각형 형태로 수의 입력이 들어옵니다.

가장 위쪽 꼭짓점의 수에서부터 왼쪽 아래, 오른쪽 아래만 계산하여 바닥에 닿았을 때,

가장 높게 획득할 수 있는 점수를 출력하면 됩니다.

옛날 문제?

문제의 출처가 무려 IOI 1994입니다. 제 나이보다 오래된 문제군요.

solved.ac 클래스 4에 속한 문제로, 같은 클래스에 속한 문제들에 비해 쉬운 편입니다.

시간 제한이 빡빡하거나 입력이 어렵지도 않습니다.

완전 탐색 식으로 풀어도 되고, DP로 풀어도 됩니다.

근데 이 문제에선 사실상 DP가 완전탐색입니다.

그런데 해당 문제에서 하나 짚고 넘어가야 할 부분이 있습니다.

깊은 복사와 얕은 복사?

DP나 BFS 문제에서는 가끔 문제를 일으키곤 하는 내용입니다.

깊은 복사란?

여러 객체(값)을 모아둔 리스트 또한 하나의 객체입니다.
따라서 독립된 메모리 주소가 존재하고, 얕은 복사는 이 메모리 주소를 새 변수에 할당하는 것입니다.
원본과 복사 리스트 모두 같은 메모리를 공유하므로,
복사 리스트의 값을 변화시킬 경우,
원본 리스트도 값의 변화가 똑같이 적용됩니다. (애초에 그냥 똑같은 놈들입니다.)

org_list = [1, 2, 3, 4]
copy_list = org_list
copy_list[0] = '이러면 안 돼'

print(org_list)

>>> ['이러면 안 돼', 2, 3, 4]

copy_list의 항목만 바꾸고 싶은데, 원본 리스트에 영향을 미쳤습니다!

깊은 복사하는 법

깊은 복사는 메모리를 공유하는 객체가 아닌,

새로운 메모리 공간에 같은 값을 가진 객체를 새로 만드는 방법입니다.

즉, 메모리나 작업 시간 효율 면에서 떨어집니다!! 그래도 어쩌겠어요!! 문제 풀어야지.

단, 2차원 이상의 배열에선 이야기가 달라집니다!!!!

리스트 내부에 리스트가 있는 경우, 깊은 복사를 통해서 가장 바깥의 리스트 객체는 새로운 메모리를 할당하더라도,

내부 리스트는 여전히 원본과 같은 메모리를 갖고 있기 때문입니다...

이 경우 deepcopy 모듈을 쓰거나, 불변 값을 요소로 가지는 최하위 배열에 접근해서 값을 복사해야합니다.

방법은 다양합니다.

.copy() 메서드 - 가장 일반적인 방법입니다.
new_list = list(org_list) - copy 메서드에 이어 가장 명시적인 방법입니다.
new_list = org_list[:] - 전체 슬라이싱 자체가 새로운 객체를 만드는 행위이므로, 이를 할당하는 방법입니다.
deepcopy 모듈 - 이 방법을 제외한 위의 방법들은 2차원 이상 배열에선 먹히지 않습니다!!!!!

어쨌든, 제일 중요한 문제를 풀어봅시다!

매우 쉽습니다.

n = int(input())
res = [int(input())]+[0]*n

for i in range(1, n):
    tmp = res[:] # .copy() 메서드를 써도 되고, 컴프리헨서를 써도 됩니다.
    num = list(map(int, input().split()))

    # 가장 왼쪽과 가장 오른쪽
    res[0] = tmp[0] + num[0]
    res[i] = tmp[i-1] + num[i]

    for j in range(1, i):
        res[j] = max(tmp[j-1], tmp[j]) + num[j]

print(max(res))