죽이고싶은 dp.... 아니 리스트... 아니 나...

먼저 2차원 리스트 생성시 진행한 실수부터 짚고 넘어가자

dp = [[0]*n]*2

이짓거리 했더니 dp[0]과 dp[1]이 동시에 변경된다. (하나만 접근해도). 아마 주소가 복사되는 형태인 듯 하다.

 

그래서 

dp = [[0]*n for x in range(2)]

이렇게 해줘야한다. 한참 머리가 아팠다..

보통의 언어들은 call by value / call by reference 둘 중 하나를 취한다.

값을 설정할 때

a = 2

b = a

이렇게 진행 할 경우 b에 2라는 값(value)이 저장되면 call by value가 되고 a의 메모리 주소(reference)가 저장되면 call by reference가 된다.

 

이를 어떻게 알 수 있냐면

b를 수정해보면 된다.  b를 수정했을 때 a도 동시에 수정된다면 call by reference, 아니면 call by value가 된다.

 

하지만 파이썬은 pass by assignment 이다.

자료형의 불변 / 가변 여부에 따라 전달방식이 다르다.

불변(immutable)객체 : int, str 등 기본형

가변(mutable)객체 : list, dict 등

 

불변 객체의 경우는  call by value,  가변 객체의 경우는 call by reference이다.

때문에 나처럼 첫 번째 방식으로 리스트를 만들어 줄 경우에는 동시에 수정될 수 밖에 없다. 

 

역시 기초가 중요한듯

 

#13398번 연속합2 https://www.acmicpc.net/problem/13398

13398번: 연속합 2

처음에는 2차원 리스트를 만들어서 진행할 생각을 했었다.

하지만 도저히 두번째 리스트를 채울 규칙이 생각나지 않아서 포기했었는데

그게 맞았다.

점점 늘고있는걸지도./..?

 

n = int(input())
nums = list(map(int, input().split()))
# 0번 리스트는 일반적인 합이다.
# 1번 리스트는 하나의 수를 제거했을 때의 합인데
# dp = [[0]*n]*2 -> 이렇게 하면 안됨. [0]에 리스트를 저장하고, 이 리스트의 주소를 [1]에 저장함.
dp = [[0]*n for x in range(2)]
dp[0][0] = nums[0]
answer = nums[0]
for i in range(1, n):
    dp[0][i] = max(dp[0][i-1] + nums[i], nums[i])
    # 특정 원소를 제거하는 경우는
    # 이미 수를 한번 제거한 합에 지금 수를 더한 경우와 -> dp[1][i-1] + nums[i]
    # 일반적인 연산에서 지금 수를 뺀 경우를 비교해야한다. -> dp[0][i-1]
    dp[1][i] = max(dp[0][i-1], dp[1][i-1]+nums[i])
    answer = max(answer, dp[0][i], dp[1][i])

print(answer)