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

Gurumee 2018. 4. 17. 12:43

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(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$ 개의 원소를 가지는 집합에서 $k$ 개의 부분집합을 고르는 조합의 경우의 수를 이항계수라 하며, $_{n}C_{k}\;$ 나 $\;^{n}C_{k}\;,\;C_{n,k}\;,C(n,k)\;,$ 또는 ${n \choose k}$ 로 나타낸다. 기호 $\;C\;$ 는 콤비네이션이라고 읽기도 한다.

그 값은 ${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단계쯤 되니까 뭔가 깊이 생각할 수록 쉽게 풀 수 있는 것 같다.

728x90

저작자표시 (새창열림)