[python] 백준 1932 - 정규삼각형

백준 1932 - [SILVER 1]

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

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

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

옛날 문제?

문제의 출처가 무려 IOI 1994다. 출제된 지 30년 됐다.

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

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

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

근데 사실상 DP가 완전탐색이다.

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

깊은 복사와 얕은 복사?

DP 문제에서는 가끔 문제를 일으키곤 하는 내용이다.

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

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

print(org_list)

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

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

깊은 복사하는 법

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

새로운 메모리 공간에 같은 값을 가진 객체를 새로 만드는 것이다.

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

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

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

내부 리스트는 여전히 원본과 같은 메모리를 갖고 있기 때문이다… 이 경우 deepcopy 모듈을 써야한다.

방법은 다양하다.

1. .copy() 메서드

   가장 일반적인 방법이다.

2. new_list = list(org_list)

   copy 메서드에 이어 가장 명시적인 방법이다.

3. new_list = org_list[:]

   전체 슬라이싱 자체가 새로운 객체를 만드는 행위이므로, 이를 할당하는 방법이다.

4. deepcopy 모듈 사용

   이는 2차원 이상의 배열에서 내부의 모든 객체를 완전히 새로 쓰고 싶을 때 쓰는 방법이다.

   즉, 이 방법을 제외한 위의 방법들은 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))