BOJ 2579 계단 오르기

문제 분석

---

문제: https://www.acmicpc.net/problem/2579

풀이 전략

---

규칙을 찾아보자. 이런류의 문제는 데이터가 1개임을 가정해보고 점차 데이터 개수를 늘려보면 경험상 규칙 찾기가 수월했다. 마치 수열문제처럼말이다.

상황 축소를 통한 규칙 찾기

계단이 하나 있다고 가정해보자. 이 계단의 값은 10이라 해보자.

그러면 이 계단을 반드시 밟아야 하니 조건에 맞는 정답은 10일 것이다.

계단이 2개 있다고 가정해보자. [10,20] 이렇게 말이다.
그러면 시작점에서 10을 밟는 선택을 할 수도 있고, 밟지 않고 20으로 바로 가는 선택이 있을 수 있다. 또, 10을 밟고, 20을 밟을 수도 있다. 조건에 맞는 정답은 30일 것이다.

계단이 3개 있다고 가정해보자. [10,20,30] 이렇게 말이다.
상황이 복잡해진다.

우리의 직관적인 접근을 통해서 우리는 50이 정답임을 알 수 있다. 그렇다면 왜?

우리의 직관을 논리적으로 설명해보자

문제 조건에서 연속될 수 있는 계단은 3개 이상일 수 없다고 했다. 그러니 최대 연속된 계단은 2개이다. => 다시 말하면 내가 n 번째 계단에 서 있을 때, 나는 n-1(직전) 계단을 밟고 온 것일 수도 있고, 그렇지 않고 n-2전전 계단에서 점프해서 온 것일 수 있다는 것이다.

왜 한 칸만 스킵하고 오냐고? 값을 최대로 만들어야하니까!

아하~ 그러면 케이스 분류가 되었다.

n-1번째 계단을 밟고 n번째 계단에 도달한 경우

n번째 계단은 무조건 밟는다. n-1번째 계단도 무조건 밟는다.

그런데 이 순간 우리는 가능한 최대 연속계단 수를 충족시켜버렸다.

즉, 이 경우에 n-1번째 계단을 밟았다는 것은 n-2번째 계단은 스킵했다는 말이 된다.

우리는 n-3번째 계단을 밟고, n-1번째 계단을 밟고, n번째 계단에 도달한 것이다.

n-3번째 계단을 어떻게 밟았는지는 중요하지 않다. 그 전에 점프를 해서 왔는지, 그 전계단을 밟고 왔는지는 상관없이 n-3번쨰 계단을 밟기만 하면 된다.

n-2번째 계단을 밟고 n번째 계단에 도달한 경우

n번째 계단은 무조건 밟는다. n-1번째 계단은 스킵한다.

n-2번째 계단은 무조건 밟는다. n-2번째 계단을 어떤 과정을 통해 밟아왔는지는 중요하지 않다. n-2번째 계단까지 온 경우들 중 최대값을 구하면 된다.

예시를 통한 이해

예시 데이터를 활용해서 이해를 마지막으로 해보자.

input	0	10	20	15	25	10
dp[0]	0	0	0	0	0	0
dp[1]	0	0	0	0	0	0

먼저 첫 번째 계단인 10(i=1)을 밟는 경우를 생각해보자.
이전 계단이 없고, 전전 계단도 없으니 dp[0][1],dp[1][1] 는 모두 10이겠다.

input	0	10	20	15	25	10
dp[0]	0	10	0	0	0	0
dp[1]	0	10	0	0	0	0

두 번째 계단인 20(i=2)을 밟는 경우를 생각해보자.
이전 계단을 밟고 오는 경우와, 전전 계단을 밟고 오는 경우가 존재한다. 그 이전 계단들은 존재하지 않으니 아래와 같이 업데이트를 하면 되겠다.

input	0	10	20	15	25	10
dp[0]	0	10	30 = 10+20	0	0	0
dp[1]	0	10	20	0	0	0

세 번째 계단인 15 (i=3)를 밟는 경우를 생각해보자.
이전 계단을 밟고 오는 경우와, 전전 계단을 밟고 오는 경우가 존재한다. 그 이전 계단들은 존재하지 않으니 (i=0인 경우) 아래와 같이 업데이트를 하면 되겟다.

input	0	10	20	15	25	10
dp[0]	0	10	30	35(0+20+15)	0	0
dp[1]	0	10	20	10+15	0	0

네 번째 계단인 25(i=4)를 밟는 경우를 생각해보자.
이전 계단을 밟고 오는 경우와, 전전 계단을 밟고 오는 경우가 존재한다.

이전 계단 15(i=3)을 밟고 오는 경우는 i=1까지 오는 경우의 최대값이 필요하다. i=1까지 어떻게 왔는지는 상관 없기 때문이다.
따라서 Math.max(dp[0][1], dp[1][1])로 최대값을 구해주자.

전전 계단 20(i=2)을 밟고 오는 경우는 i=2까지 오는 경우의 최대값이 필요하다. 따라서 Math.max(dp[0][2], dp[1][2])로 최대값을 구해주고 테이블을 업데이트해주자.

input	0	10	20	15	25	10
dp[0]	0	10	30	35	Max(10,10) + 15+25	0
dp[1]	0	10	20	25	Max(30,20)+25	0

이제 규칙이 보이는 듯하다.

구현

여기까지 생각이 도달했다면 여러분은 DP네...라고 생각이 들었을 것이다.

우리가 고려할 수 있는 케이스가 2가지니, row는 2개로, column수는 들어오는 데이터 개수 +1 개로 2차원 배열을 만들자.

0번째 row는 n-1번째 계단을 밟고 오는 케이스로,

1번째 row는 n-2번째 계단을 밟고 오는 케이스의 값을 저장할 것이다.

const input = require('fs').readFileSync(0).toString().trim().split('\n').map(Number)
const N = input[0]

const dp = Array.from({ length: 2 }, () => Array.from({ length: N + 1 }, () => 0))

이제 계단을 순서대로 순회하며 DP 테이블을 업데이트 시켜주자. 우리가 이전에 예시를 통해 살펴본 그대로 구현만 하면 된다.

포인트는 ~ n번째 계단은 반드시 밟는 다는 것! 그리고 n번째 계단의 dp 테이블을 업데이트 할 때 n-2와 n-3번째 계단까지 어떻게 왔는지는 이미 테이블에 저장되어 있기에, 최적의 결과를 위해 최대값을 활용한다는 점이다.

구현해보자. 잘 될거다.

성공한 풀이

---

const input = require('fs').readFileSync(0).toString().trim().split('\n').map(Number)
const N = input[0]

const dp = Array.from({ length: 2 }, () => Array.from({ length: N + 1 }, () => 0))
dp[0][1] = input[1]
dp[1][1] = input[1]
dp[0][2] = input[1] + input[2]
dp[1][2] = input[2]

for (let i = 3; i < N + 1; i++) {
  dp[0][i] = Math.max(dp[0][i - 3], dp[1][i - 3]) + input[i - 1] + input[i]
  dp[1][i] = Math.max(dp[0][i - 2], dp[1][i - 2]) + input[i]
}

console.log(Math.max(dp[0][N], dp[1][N]))

회고

---

일 년 전쯤 푼 문제인데도 다시 보니 새로웠다. DP문제는 확실히 수열문제같은 느낌이 있다. 풀면 풀수록 규칙이 잘 보이는 듯 하다.

재취업을 하려니 쉽지 않다. 서류는 넣는 족족 탈락하고, 집에서도 걱정하는 눈치다. 현대오토에버 코딩테스트를 보고 결과를 기다리고 있다는 게 그나마 위안이 된다.

퇴사 후 하고 싶은 개발 공부를 잘 하고 있으니 그걸로 족하다 생각했었다. 그렇지만 시간이 지나가니 내 성장과는 별개로 현실적인 것들이 보이기 시작했다. 점점 나이가 들어가시는 부모님, 줄어드는 내 통장 잔고... 내 스스로를 책임지는 것이 내 이상을 이루는 일보다 앞서서 괴리감이 생긴 느낌이다.

이럴 때일수록 내가 할 수 있는 일을 잘 하는 것도 나를 진정으로 위하는 방법이라 믿는다.