[프로그래머스] 멀리 뛰기

문제요약

효진이는 멀리뛰기를 1칸 혹은 2칸 할 수 있는 아입니다.
칸의 개수를 줄 테니 효진이가 이 칸들을 건너가는 방법의 수를 구하세요.

아이디어

2년 전에 계단 n 칸을 오르는데 다리가 길어서 한번 다리를 벌릴 때 1,2,3,4칸 중에 선택할 수 있는 사람이 계단을 오를 수 있는 경우의 수를 고르라는 문제를 풀었었다. 매우 똑같다...

n칸이 주어졌을 때
case1. 1칸을 건너보고 나머지 n-1칸을 건널 수 있는 방법의 수를 고민
case2. 2칸을 건너보고 나머지 n-2칸을 건널 수 있는 방법의 수를 고민

바텀업 방식으로 풀기 좋은게 3칸이라 하면 1칸 방법 고민, 2칸 방법 고민
이런 식으로 n보다 작은 답을 가지고 활용해서 n칸에 대한 답을 만들면 되기 때문이다.

주의할 점

c++로 풀었을 때 bottom up 테이블을 long long으로 만들기를 권장한다. 근데 사실 int로 해도 상관 없다.(가짓수에 대해 1234567로 나누는데 값1과 값2를 더해봤자 1234567*2보다 작기 때문이다. 이런 문제의 경우 곱셈이 들어가는 경우가 많으니 long long으로 하는 습관을 들이는 것도..)

코드

#include <string>
#include <vector>

using namespace std;
//bottom up solution
long long tab[2001];//n칸이 주어졌을 때 만들 수 있는 가짓수

long long solution(int n) {
    long long answer = 0;
    tab[1] = 1;
    tab[2] = 2;
    for(int i = 3;i<=n;i++){
        tab[i]= (tab[i-1]+tab[i-2])%1234567; 
    }
    answer= tab[n];
    return answer;
}