문제

2579번 - 계단 오르기

풀이

처음 시도엔 이 문제의 중요한 포인트를 잡지 못해서 헤맸다.

이 문제는 dp인데, 단순히 합만 생각할 것이 아닌 1단 점프인지 2단 점프인지도 생각해야하는 문제다.

n번째의 칸을 밟기 위해서는 n-2번 칸에서 2단 점프 또는 n-1번 칸에서 1단 점프 이렇게 두 개의 방법밖에 존재하지 않는다.

그런데 문제에서 주어진 조건을 보면 3칸을 연속으로 밟는게 안된다고 했다. 이 말은 1단 점프를 연속 2번 뛰면 안되는 말과 같다.

위에 n번째 칸을 밟기 위한 방법 중 n-1번 칸에서 1단 점프가 딱 한 틱 이전인 n-1칸을 사실 n-2칸에서 1단 점프해서 왔더라면, n칸은 n-2 -> n-1 -> n 이렇게 1단 점프 2번으로 불가능한 이동 방법이 된다.

분명 n번째의 칸을 밟기 위해서는 n-2번 칸에서 2단 점프 또는 n-1번 칸에서 1단 점프 이렇게 두 가지 안이 있다는 건 확실하다. n-2번 칸에서 2단 점프는 조건에 반하는 것이 없으므로, n-1번 칸에서 1단 점프의 경우를 조건에 맞게 고치려면 어떻게 다르게 생각하면 될지가 관건이다.

바로 앞에서 n-2 1️⃣↗️ n-1 1️⃣↗️ n이렇게 1단 점프 두번이 안된다고 했다. 그러면 2단 점프 + 1단 점프 후 도착한 지점이 n이라고 한다면 조건을 위반하지 않게 된다. 즉 n-3 2️⃣↗️ n-1 1️⃣↗️ n의 이동 방법이라면 가능한 것이다.

이렇게 n-1번 칸에서 1단 점프 => n-3번 칸에서 2단 점프 후 n-1번 칸에서 1단 점프 로 조건을 바꿔 n번째 칸에 도달하기 위한 1단, 2단 점프의 조건을 만들어낼 수 있는 것이다.

더 나아가서

이 문제의 해법은 이렇게 두 가지 조건으로 나눌 때, 나눠진 조건이 연속이어도 조건에 위배되지 않도록 조건을 짜는 것이다.

처음 생각해낸 조건인 n-1번 칸에서 1단 점프는 이전 칸에서도 이 조건으로 점프되었다면 2번 연속일 경우 조건에 위배된다.

두번째 생각해낸 조건인 n-3번 칸에서 2단 점프 후 n-1번 칸에서 1단 점프는 연속되어도 조건을 만족한다. n-6 2️⃣↗️ n-4 1️⃣↗️ n-3 2️⃣↗️ n-1 1️⃣↗️ n 이런 식으로 연속해도 조건에 맞는다는 뜻이다.

또 다르게 생각해보면 조건 위배 없이 가능해지게 하는 2단 점프를 끝에 넣기만 하면 되는 것이기도 하다. 처음 1단 점프만 생각했을 땐 조건 불만족이었지만, 그 이전 점프를 2단 점프로 뛰었다면 조건을 만족했던 것처럼 말이다.

쉽게 이해하려면, 레고 블록을 생각하면 된다. 레고의 앞면과 뒷면은 돌출부와 함몰부로 나뉘어있다. 레고를 층층히 쌓을 수 있는 이유는 돌출 + 함몰이 맞물려 고정되어 쌓을 수 있는 것이다.

만약 돌출 + 돌출로 쌓으려고 하면 맞물리지 않는 것처럼, 이 문제도 2단 점프가 함몰이고 1단 점프가 돌출로 맞물리는 구조라고 생각되었다.

만약 문제 조건에서 4칸 연속이 불가능하다고 했다면 2 + 0*1, 2 + 1*1, 2 + 2*1이렇게 3가지의 레고 블록이 만들어지겠다. 그래서 연습해보려고 비슷한 문제를 찾아보려 했는데, 아직 못찼았다..

점화식

문제를 풀기 위해 n-3의 최적값이 필요하기 때문에, 0, 1, 2번의 dp 배열을 채워야한다.

dp[0] = 0번 계단(시작위치가 아니라 시작에서 한칸 올라간 칸의 점수)
dp[1] = max(0번 뛰어넘고 바로 1번 밟는 점수, 0번 + 1번의 1단 점프 점수)
dp[2] = max(0번 + 2번의 2단 점프 점수, 1번 + 2번의 1단 점프 점수)

풀이

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'e.txt';
const input = require('fs')
	.readFileSync(filePath)
	.toString()
	.trim()
	.split('\n')
	.map(Number);

const stareCount = input.shift();

const dp = new Array(stareCount).fill(0); // 최적해를 저장하기 위한 공간

dp[0] = input[0];
dp[1] = Math.max(input[0] + input[1], input[1]);
dp[2] = Math.max(input[1], input[0]) + input[2];

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

console.log(dp[input.length - 1]);

결과

설명에 오류가 있거나 이해가 어려운 부분이 있으면 댓글이나 이메일(pigkill40@naver.com)로 문의해 주시면 도움을 드리겠습니다.