백준 9095 1, 2, 3 더하기

문제

제한사항

입출력 예

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const n = +input.shift();

const solution = (N) => {
  let answer = [0, 1, 2, 4];
  for (let i = 4; i <= 11; i++) {
    answer.push(answer[i - 1] + answer[i - 2] + answer[i - 3]);
  }

  return answer[N];
};

for (let x of input) {
  console.log(solution(+x));
}

다이나믹 프로그래밍으로 풀 수 있다.

1칸, 2칸, 3칸씩을 올라 갈 수 있는 계단 오르기로 바꿔서 생각해보자.

1번칸에 올라가는 방법 1개
2번칸에 올라가는 방법 2개
3번칸에 올라가는 방법 4개 => 1번에서 두칸 올라가기 + 2번에서 1칸 올라가기 + 한번에 3칸 올라가기

4번칸에 올라가는 방법은 ?
1번 칸에서 세칸 올라가기 + 2번 칸에서 두칸 올라가기 + 3번 칸에서 한칸 올라가기 즉 dp[1] + dp[2] + dp[3]이 된다.

다른풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(e => +e);
let n = input.shift();

let arr = [1, 2, 3];

const solution = (m, arr) => {
  let answer = 0;
  const dfs = (L, sum) => {
    if (sum > m) return;
    if (sum === m) {
      answer++;
    } else {
      for (let i = 0; i < arr.length; i++) {
        dfs(L + 1, sum + arr[i]);
      }
    }
  };
  dfs(0, 0);
  return answer;
};

for(let x of input){
    console.log(solution(x,arr));
}

• 깊이 우선 탐색 방식으로 풀었다.
• 입력이 크지 않아서 가능했다.