[python] 백준 2579 - 계단 오르기

출처 : 백준, https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

이거 한국정보올림피아드 지역부 본선 초등부 문제인걸 알면 얼마나 많은 사람들이 절망에 빠질까

일단 난 빠졌다..........

 

 

첫 번째 풀이 : 실패

 

if __name__ == '__main__':
  n = int(input())
  stairs = [int(input()) for _ in range(n)]

  visited = [-1] * n

  visited[n-1] = 1
  stairs[n-1] *= -1

  while True:
    if max(stairs) <= 0:
      break
      
    max_index = stairs.index(max(stairs))

    if max_index - 2 >= 0 and visited[max_index - 2] == 1 and visited[max_index - 1] == 1:
      stairs[max_index] = 0
      continue

    if max_index - 1 >= 0 and max_index + 1 < n and visited[max_index - 1] == 1 and visited[max_index + 1] == 1:
      stairs[max_index] = 0
      continue


    if max_index + 2 < n and visited[max_index + 1] == 1 and visited[max_index + 2] == 1:
      stairs[max_index] = 0
      continue

    stairs[max_index] *= -1
    visited[max_index] = 1

  print(-sum(stairs))

 

값이 큰 거 먼저 취하면서 취한 값이 연속으로 3개가 안 이어지도록 하는 풀이이다.

정답에 최댓값이 포함이 안 될 경우를 고려하지 못해서 틀렸다.

 

 

두 번째 풀이 : DP 풀이

 

if __name__ == '__main__':
  n = int(input())
  stairs = [int(input()) for _ in range(n)]
  
  score_arr = [[0, 0] for _ in range(n + 1)]

  score_arr[1][0] = stairs[0]
  score_arr[1][1] = stairs[0]

  if n >= 2:
    for i in range(2, n+1):
      score_arr[i][0] = max(score_arr[i-2][0], score_arr[i-2][1]) + stairs[i-1]
      
      score_arr[i][1] = score_arr[i-1][0] + stairs[i-1]

  print(max(score_arr[n][0], score_arr[n][1]))

 

Dynamic Programming은 순환식을 작성해서 순환식을 코드화 하는 풀이방법이다.

먼저 순환식을 작성하기 위해서 어떤 방식으로 순환식을 작성할 지 생각해봤다.

 

 

다음과 같은 계단이 있다면 2번 계단을 도달할 수 있는 경우의 수는

0번 계단에서 2번 계단으로 올라가거나 아니면 1번 계단에서 2번 계단으로 올라가는 것 2가지이다.

이 두 가지 중 큰 것 + 올라갈 계단의 값이 최댓값이라는 다음과 같은 가정을 세우고 순환식을 풀기 위해 직접 작성해봤다.

 

S(i) = max(S(i-1), S(i-2)) + stairs[i] (i>1), S(0) = 0, S(1) = stairs[0]

 

계단 i의 값은 편의를 위해 i만 표기, S(0) = 0, S(1) = 1

S(i)	S(i-2) + stairs[i]	S(i-1) + stairs[i]	S(i-1) + stairs[i]????
S(0)	-	-
S(1)	-	-
S(2)	0 + 2	1 + 2
S(3)	1 + 3	2 + 3
S(4)	1 + 2 + 4	1 + 3 + 4	2 + 3 + 4
S(5)	1 + 3 + 5	2 + 3 + 5	1 + 2 + 4

 

굵은 글씨로 최댓값 후보가 될 수 있는 것들을 나타내보았다.

문제는 S(2)에서도 순환식이 성립하지 않으며,

그 외에도 계단을 올라가면서 S(i-1) 값이 2개가 나오게 되며 순환식이 성립하지 않게 된다.

그래서 S(i)값이 2개라는 가정을 하고 다시 작성해보았다.

 

계단 i의 값은 편의를 위해 i만 표기, S(0) = [0, 0], S(1) = [1, 1]

S(i)	S(i-2)[0] + stairs[i]	S(i-2)[1] + stairs[i]	S(i-1)[0] + stairs[i]	S(i-1)[1] + stairs[i]
S(0)	-	-	-	-
S(1)	-	-	0 + 1	0 + 1
S(2)	0 + 2	0 + 2	1 + 2	1 + 2
S(3)	0 + 3	1 + 3	2 + 3	1 + 2 + 3
S(4)	2 + 4	1 + 2 + 4	1 + 3 + 4	2 + 3 + 4
S(5)	1 + 3 + 5	2 + 3 + 5	1 + 2 + 4 + 5	1 + 3 + 4 + 5
S(6)	1 + 2 + 4 + 6	1 + 3 + 4 + 6	S(4) + 5 + 6	1 + 2 + 4 + 5 + 6

 

위 표를 보면 S(3)부터는 마지막 값이 3개를 연속해서 밟는 값이 되어 max값에 포함되지 못하고,

S(5)부터 앞의 3개 값 중 max값이 S(i)의 값이 된다는 것을 알 수 있다.

어짜피 S(2)부터 앞의 3개를 비교해도 최댓값이 나오기 때문에 순환식을 다음과 같이 세워볼 수 있다.

 

S(i) = max(S(i-2)[0], S(i-2)[1], S(i-1)[0]) + stairs[i] (i>1), S(0) = [0, 0], S(1) = stairs[1, 1]

 

그리고 이 순환식을 그대로 코드로 구현한 것이 위의 풀이이다.

 

---

 

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

DP 너무 어렵다.