Baekjoon 2579번 계단 오르기

문제

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

걸린 시간

01 : 15 : 49

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n;
int stairs[301];
int cache[3][301];

int upStairs(int cur, int floor){
    // 기저 사례
    if(floor == n)
        return stairs[floor];
    // 메모이제이션
    int& ret = cache[cur][floor];
    if(ret != -1)
        return ret;
    // 재귀 호출
    int one = 0, two = 0;
    if(cur <= 1){
        one = upStairs(cur+1, floor+1)+stairs[floor];
        if(floor+2 <= n)
            two = upStairs(1, floor+2)+stairs[floor];
    }
    if(cur == 2)
        if(floor+2 <= n)
            two = upStairs(1, floor+2)+stairs[floor];
    return ret = max(one, two);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    memset(stairs, 0, sizeof(stairs));
    for(int i = 1; i < n+1; i++)
        cin >> stairs[i];
    memset(cache, -1, sizeof(cache));
    cout << upStairs(0, 0) << "\n";
    return 0;
}

손으로 문제를 풀어볼 땐 최대한 보기 쉽게 그려야 빠르게 직관을 얻을 수 있다. 문제에 나온 계단 사진으로 재귀 호출 과정을 생각하려고 하면 잘 그려지지 않는 것이 당연하다.

TypeScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map((s: string) => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const n: number = parseInt(input());
const stair: Array<number> = [];
const dp: Array<Array<number>> = Array.from(Array(n+1), () => Array(3+1).fill(0));

for(let i = 0; i < n; i++){
  const p: number = parseInt(input());
  stair.push(p);
}

const solve: Function = (idx: number, cnt: number): number => {
  // 기저 사례
  if(idx === n-1 && cnt < 3) return stair[idx];
  // 메모이제이션
  if(dp[idx][cnt]) return dp[idx][cnt];
  // 재귀 호출
  let ans: number = 0;
  if(idx < n && cnt < 3){
    let first = solve(idx+1, cnt+1);
    let second = solve(idx+2, 1);
    ans = Math.max(first, second)+stair[idx];
  }
  if(ans) return dp[idx][cnt] = ans;
  else return Number.NEGATIVE_INFINITY;
}

console.log(Math.max(solve(0, 1), solve(1, 1)));

마지막 도착 계단은 반드시 밟아야 한다는 조건을 처리해주지 않아 여러번 틀렸다.