백준 2156 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

문제를 보자마자, 이전에 풀었던 계단 오르기 문제가 생각났다.
 
하지만 계단 오르기 문제에서는, 마지막 계단을 반드시 밟아야 한다는 전제 조건이 있었기에, 기준점을 잡고 풀 수 있었다.
 
이번 문제는 해당 조건이 없어 당황했다.
 
배우는 입장에서 여러 타입의 문제가 나올수록 좋다.
 
당장 느끼는 감정은 답답하지만, 훗날을 위해.
 
이번 문제를 풀며 가장 막힌 건, 패턴 찾기보단, 배열의 크기 선언이다.
 
코드 

a= int(input())

array=[0] * 10000

dp=[0] * (a+2)

for i in range(a):

    array[i] =int(input())

dp[0] = array[0]

dp[1] = array[0] + array[1]

dp[2] = max(array[0]+array[2],array[1]+array[2],dp[1])

       

for i in range(3,a):

    dp[i] = max(dp[i-2]+array[i],dp[i-3]+array[i-1]+array[i],dp[i-1])

print(max(dp))

수많은 시도를 했다.
 
dp부분은, n이 3 이상인 특정 한 부분을 잡았을 때, 총 3가지 경우가 존재한다.
3가지가 연속으로 올 수 없기에,
 
1. dp [i-2] + array [i]
2. dp [i-1]
3. dp [i-3] + array [i-1] + array [i]
 
근데 문제가 생겼다.
 
dp [i-3] + array [i-2] + array [i]
를 넣어봤는데 문제가 해결되지 않았다.
 
이유가 뭔지 계속 탐구하고 있지만, 해결되지 않는다.
 
추후 이해를 마치고 나머지 부분을 포스팅하겠다.
 
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 
펜으로 조금 끄적이다가 발견했다.
 
dp [i-3] 다음에 array [i-2]를 더하면 그냥 dp [i-2]가 된다.. 그래서 겹치는 부분이 발생하기에 필요 없는 연산이다.
 
근데 그냥 겹치기만 하는 거면 추가한다고 해도 상관없지 않나..? 란 생각이 든다.
 
이것도 해결되면 추후에 더 작성하겠다.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
dp 계산이 아직 완전히 수행되지 않은 상태에서,
dp [i-3] + array [i-2] + array [i] 부분이 계산되면 뜻하지 않는 계산값이 출력된다.

왜냐하면 dp[i-3] 의 최댓값을 계산할 때
array[i-4]가 포함되었을 수도 있기에 예외가 발생한다.
 
따라서 해당 부분을 삭제해야한다.
 
배운 점
1. dp 문제를 더 열심히 공부해야겠다는 방향성을 배웠다.