[ BOJ / 파이썬] 2579 계단 오르기

정말 간만에 PS문제 푸니까 또 재밌고 할 만한 것 같다.

그리고 조금 원리를 이해해서 푸는 느낌이 나니 문제 풀이력이 느는 느낌이 확실히 든다. 

역시 일이 진행되다가 너무 답도 없이 고여버리면 잠시 쉬고 오는 것도 ( 노는게 아니라 비슷한 다른 일 ..^^) 좋은 것 같다.

사담은 여기까지 하고,

 

 

우선 해당 문제가 DP라는 정보를 알고 부딪힐 수 있었다. 그래서 더 답에 빠르게 가까워진 것 같다.

1. DP테이블을 어떻게 구성할 지, 어떤 내용을 담을 지를 결정하고,

2. 점화식을 세우고

3. 초기값을 셋팅하는 식으로 풀어라 라고 배웠다.

 

되게 초보자 티 내는 듯이, DP테이블을 무조건 1차형으로 사용해야한다고 생각했다. 문제 풀이 경험의 부족 때문일 것이다.

이 값을 갖는 계단이 n개 있으므로 1줄의 배열이 완성된다.

 

그리고 각 계단에서 가지는 값은 2개다. 왜냐하면 그 계단이 연속된 3번째 계단이 아니어야 하기 때문이다.

해당 계단은 연속된 1번째 계단일 경우, 연속된 2번째 계단인 경우로 나뉘어 2가지 값을 갖는다.

그리고 각 정보가 모두 다음에도 필요하기에 그 값을 각각 저장하기 위해 2차원 배열로 설정하는 것이다.

 

여기서 3번째 계단부터 계산이 이루어져야 한다. 그 전까지의 값은 앞으로의 점화식과는 다르다. 

왜냐하면 1번째 계단일 경우는 본인 값 바로 리턴하고, 2번째 계단일 경우는 2개의 계단 값을 합쳐 리턴하면 끝나기 때문이다. 특히, 위에서 가정한 점화식에서는 [해당 계단 - 2]의 값을 참조할 필요가 있는데 1과 2는 그게 불가능하기 때문이다.

이 경우는 각 값으로 예외처리해서 연산을 그저 끝내버린다.

 

각 계단의 값에 대해 다른 점화식을 세워야 한다. 그게 이 문제의 포인트. 이 계단이 K번째 계단이라고 설정.

우선 해당 계단이 연속된 1번째 계단일 경우 = 연속되는 계단이 아니라는 뜻. 그러니까 K-1번째 계단을 안 밟았어야 한다. 그리고 K-2는 밟았을 것이다. 규칙 상은 안 밟아도 상관 없지만, 최대값을 구하기 위해서는 밟는 것이 가능한 K-2번째는 밟으면 좋은 거니까 밟아야한다고 볼 수 있다. K-2가 연속되어 밟힌거든 아니든 K에게는 영향을 끼치지 않는다. 그래서 그 중 최댓값을 받아오고, 내 계단의 값을 더해준다.

다음 해당 계단이 연속된 2번째 계단일 경우는 무조건 K-1의 계단을 밟아야한다. 그래야 그 다음인 K번째 계단을 밟았을 때 2번째로 연속된 상태가 되니까. 여기서 K-2에서 가져올 값은 무조건 K-1의 1개 밟은 값이다. 2개 밟은 값을 가져와 내것까지 채워넣으면 그건 3번째 밟은거니까 규칙 위반이라서 값 저장이 불가능하다. 그건 무시하기 위해 K-1에서는 1개 밟은 상태일 때의 값을 가져와 내 값을 더하기만 하는 것이다.

 

그렇게 쭉 흘러가서 DP테이블을 채운 뒤, 마지막 값의 1번째 연속으로 밟아진 값과 2번째 연속으로 밟아진 값 중 더 큰 값을 출력하면 된다.

 

 

/  1 번째 제출  /

import sys
input = sys.stdin.readline

n = int(input())

stairs = [0]*(n+1)
for i in range(1, n+1):
  stairs[i] = int(input())

dp = [[0]*3 for _ in range(n+1)]

dp[1][1] = stairs[1]
dp[1][2] = 0
dp[2][1] = stairs[2]
dp[2][2] = stairs[1] + stairs[2]

for k in range(1, n+1):
  dp[k][1] = max(dp[k-2][1], dp[k-2][2]) + stairs[k]
  dp[k][2] = dp[k-1][1] + stairs[k]

print(max(dp[n][1], dp[n][2]))

 

: 당황스럽게도 틀렸다.

: 이유는 예외처리를 하지 않아서. 
: 설명에도 얘기했듯이 계단 1개일 때, 2개일 때는 본인보다 작은 값은 건드리면 안 된다. 그런데 1개 일 때, 2개일 때를 포함해서 점화식에 넣어버리는 실수를 했다. 그래서 해당 케이스에 틀렸다는 결과를 얻었다고 추측한다. (8-90퍼에서 틀렸습니다 뜨면 이 경우 의심해야할 것이다.)

 

 

/  2 번째 제출  /

import sys
input = sys.stdin.readline

n = int(input())

stairs = [0]*(n+1)

for i in range(1, n+1):
  stairs[i] = int(input())

if n == 1:
  print(stairs[1])
  exit(0)
if n == 2:
  print(stairs[1]+stairs[2])
  exit(0)

dp = [[0]*3 for _ in range(n+1)]

dp[1][1] = stairs[1]
dp[1][2] = 0
dp[2][1] = stairs[2]
dp[2][2] = stairs[1] + stairs[2]

for k in range(1, n+1):
  dp[k][1] = max(dp[k-2][1], dp[k-2][2]) + stairs[k]
  dp[k][2] = dp[k-1][1] + stairs[k]

print(max(dp[n][1], dp[n][2]))

 

 

 

/  다른 사람 코드  /

n=int(input())

graph=[0]*300
for i in range(n):
    graph[i]=int(input())

dp=[0]*300

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

for i in range(3,n):
    dp[i]=max(dp[i-2]+graph[i],dp[i-3]+graph[i-1]+graph[i])

print(dp[n-1])

 

: n 범위가 300 이라서 그냥 300 배열 할당해버리고,

: 1차원으로 해결해버리셨다.

: 0~3개까지는 초기값으로 할당하셨고.

: for문을 돌 때는 graph[i]는 빼는게 더 좋아보인다. 중복되니까.

: for문에서는 어차피 이전까지의 값이 최대일 거라 생각하고, max에서는 이번거가 1개째 연속일 때와, 2개째 연속일 때로 2가지 경우를 나눴다. 2개째 연속일 때는 만약 i-1이 i-2라면 계산 후보에도 못 넣고, 그 전 값을 포함했다면 안 포함했을 것이라는 생각에 i-3을 더해준 것 같다.

: 스스로 사고방식에 근거했을 때 저는 조..금 실수하기, 헷갈리기 좋은 생각인 것처럼 느껴진다.

: 그런데 이게 좀 더 쉽게 이해하기 쉬운 풀이인지, 다른 해답을 보면 거의 이렇게 하셨네.

 

---

2022.10.06

코테 감 약간 잡히고 다시 복습 중인데 밑에 있는 풀이가 훨씬 직관적이고 이해가 쉽다. 왜 저렇게 풀었나 했는데 이제 이해가 간다.

 

import sys
input = sys.stdin.readline

n = int(input())
stairs = []
for i in range(n+1):
  stairs.append(int(input().strip()))
dp = [0]*(n+1)

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

for i in range(3, n):
  dp[i] = max(dp[i-2]+stairs[i], dp[i-3]+stairs[i-1]+stairs[i])

print(dp[n-1])

# 런타임에러

위의 방식으로 받았더니 런타임에러가 났는데 . 아 왜? 싶어서 MAX값의 문제인가 했는데 

세상에... 예상치도 못하게..

dp테이블은 보다시피 stairs의 값을 받아와서 저장한다. 그런데 이 때 stairs가 2개 이하라면 참조할 값이 없어서 인덱스에러가 나는거였다.... 

매번 인덱스 에러의 상한만 고려했는데 하한에서 걸리다니.. 대박.. 유의하자..

그래서 다들 stairs를 미리 0으로 맞춰서 고정으로 두고 값을 후에 변경하는거였구나..

 

import sys
input = sys.stdin.readline

n = int(input())
stairs = [0]*300
dp = [0]*300
for i in range(n):
  stairs[i] = int(input())
dp[0] = stairs[0]
dp[1] = dp[0] + stairs[1]
dp[2] = max(stairs[0], stairs[1]) + stairs[2]

for i in range(3, n):
  dp[i] = max(dp[i-2]+stairs[i], dp[i-3]+stairs[i-1]+stairs[i])

print(dp[n-1])