[프로그래머스 3단계] 알고리즘 29. 멀리 뛰기

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 29. 멀리 뛰기 

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 출력하는 jumpCase 함수를 완성하세요. 예를 들어 4가 입력된다면, 5를 반환해 주면 됩니다.

#include<iostream>

#include<vector>

using namespace std;

int jumpCase(int n)

{

    int answer = 0;

    return 0;

}

int main()

{

    int test = 4;

//아래는 테스트로 출력해 보기 위한 코드입니다.

    cout << jumpCase(test);

}

풀이:

이 문제의 핵심은 2칸의 개수에 따른 점프를 뛸 수 있는 상황의 개수를 구하는 것이다. 무슨 말이냐면 예를 들어서 효진이가 2칸 뛰는 것을 1번 한다고 해보자 그럼 상황은

2, 1, 1

1, 2, 1

1, 1, 2

이렇게 3가지이다. 점프 3번중 어디에서 2번째를 1번 뛰는지에 따라 상황이 바뀐다. 예 하나를 들어보자. 이번엔 5칸일 때다. 그럼 효진이가 뛸 수 있는 상황은 다음과 같다.

2번 뛰기 횟수 0

1 1 1 1 1

2번 뛰기 횟수 1

2 1 1 1

1 2 1 1

1 1 2 1

1 1 1 2

2번 뛰기 횟수 2

2 2 1

2 1 2

2 2 1

뭔가 규칙이 보이는가? 수학을 조금 할 줄 아는 사람이라면 쉽게 접근을 할 지 모르겠다. 이 문제의 핵심은 '조합'이다. wiki에서 조합이란 다음과 같다.

$$ n {\displaystyle n} 개의 원소를 가지는 집합에서 $$ k {\displaystyle k} 개의 부분집합을 고르는 조합의 경우의 수를 이항계수라 하며, $$ n C k {\displaystyle _{n}C_{k}\;} 나$$ n C k , C n , k , C ( n , k ) , {\displaystyle \;^{n}C_{k}\;,\;C_{n,k}\;,C(n,k)\;,} 또는 $$ ( n k ) {\displaystyle {n \choose k}} 로 나타낸다. 기호 $$ C {\displaystyle \;C\;} 는 콤비네이션이라고 읽기도 한다.

그 값은 $$ ( n k ) = P ( n , k ) k ! = n ! k ! ⋅ ( n − k ) ! {\displaystyle {n \choose k}={\frac {P(n,k)}{k!}}={\frac {n!}{k!\cdot (n-k)!}}} 이다.

이를 코드로 표현해보면 다음과 같다.

int combinate(int n, int k){

   if (1 == k)

return n;

else if(n == k)

return 1;

else

return combinate(n-1, k-1) + combinate(n-1, k);

}

다시 문제로 돌아가자. 이 문제는 2칸의 뛰는 횟수에 따라서 이렇게 나타낼 수 있다. n=4와 n=5일 때를 들어보겠다.

n=4

k=0

1111

k=1

2 1 1

1 2 1

1 1 2

count = combinate(4-1, 1)

k=2

2 2

count = combinate(4-2, 2)

n= 5

k=0

1 1 1 1 1

k=1

2 1 1 1

1 2 1 1

1 1 2 1

1 1 1 2

count = combinate(5-1, 1)

k=2

2 2 1

2 1 2

1 2 2

count = combinate(5-2, 2)

2칸 뛰는 횟수 k번에 대해서 길이가 n을 넘지 않을 때 횟수를 다음과 같이 식을 만들 수 있다.

jumpCase(n) = 1 + combinate(n-1, 1) + combinate(n-2, 2) + combinate(n-k, k) (단, n-k >= k)

코드로 나타내면 다음과 같다.

int jumpCase(int n)

{

    int answer = 1; //situtation all one step jump

    //k is two steps jump's count

for (int k=1; k*2 <= n; k++){

answer += combinate(n-k, k);    //situations : k-th two step jump's situations

}

    return answer;

}

이렇게 해서 3단계 2번째 문제도 간단하게 풀 수 있었다. 확실히 3단계쯤 되니까 뭔가 깊이 생각할 수록 쉽게 풀 수 있는 것 같다.