백준 2579 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.

해당 부분 지적 감사히 받습니다.

 

문제를 보자.

문제가 길다.

 

그래도 문제를 읽고 풀이를 생각하며, 내가 발전했구나 생각은 들었다.

 

바로 DP생각이 났기 때문이다.

 

재미를 느꼈다.

 

공부를 하거나, 운동을 하거나 등등 무언가를 성취하기 위해서 겪어야 하는 과정은 항상 힘들다.

 

내가 노력하고 투자한 시간의 결과가 즉각적으로 보이지 않기 때문이다.

 

그래서 이 순간이 소중하다.

 

적지만 DP 문제들을 접하며 나는 3가지로 프로세스를 분리했다.

 

1. DP로 풀 수 있는 문제인지 확인

2. 어떠한 패턴을 가지는지 확인

3. 코드 구현

 

나와 다른 모든 사람들이 2번에서 가장 힘들어할 것이라 생각한다.

 

착각일 수 있지만, 적어도 나는 그렇다.

 

코드

a = int(input())

array= [int(input()) for _ in range(a)]

dp = []

if len(array) >= 1:

    dp.append(array[0])

if len(array) >= 2:

    dp.append(max(array[0]+array[1],array[1]))

if len(array) > 2:

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

for i in range(3,a):

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

   

print(dp.pop())

사실 다른 코드는 설명할 필요가 없다고 생각한다.

 

for i in range(3,a):

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

이 부분에 대해서만 설명하겠다.

 

a=6, 1, 2, 3, 4, 5, 6의 경우로 보겠다.

 

문제 조건중에 반드시 마지막 계단은 밟아야 한다는 조건이 있었다.

 

그렇다는 건 반드시 6은 찍어야 한다.

 

또한, 연속된 3개의 계단을 밟을 수 없다.

 

그럼 5를 밟았을 경우, 4를 밟았을 경우 총 2가지로 나눌 수 있다.

 

5를 밟았을 경우 4는 밟을 수 없다.

 

따라서 dp [i-1] + array [i-1] + array [i]라는 식이 나오게 된다.

 

4를 밟았을 경우 5를 밟을 수 없다.

 

따라서 dp [i-2] + array [i]라는 식이 나오게 된다.

 

위 두 개의 식으로 점화식을 세울 수 있다.

 

이 문제를 해결함과 동시에, 또 소중한 순간이 찾아왔다.

 

재미있다.

 

아 그리고 이 포스팅을 마지막으로 2주 정도는 포스팅이 없을 수 있다.

 

시험기간이다.

 

배운 점

1. DP문제에서 점화식을 세우기 위해 예외 없는 모든 경우의 수를 고려해야 한다.