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

문제

효진이가 멀리 뛰기를 연습하고 있다.

효진이는 한번에 1칸, 또는 2칸을 뛸 수 있다.

 

멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝까지 도달하는 방법이 몇 가지인지 알아내고

여기에 1234567을 나눈 나머지값을 반환하는 함수를 만들어야 한다.

 

 

제한사항

1. n은 1이상 2,000이하인 정수이다.

 

 

코드

from math import factorial

def combination(n, r):
    return factorial(n) // (factorial(r) * factorial(n-r))

def solution(n):
    answer = 1
    i = 1
    while i <= n-1:
        answer += combination(n-1, i)
        n -= 1
        i += 1
    
    return answer % 1234567

 

 

설명

우선 모든 수는 1칸씩 뛰어서 끝까지 도달할 수 있기 때문에 이 경우는 무시한다.

 

프로그래머스 문제 사이트에서 예시로 든 n=4인 경우를 살펴보면서 어떻게 문제를 풀건지 확인해본다.

n = 4 일 때,

(1칸, 1칸, 1칸, 1칸),

(1칸, 1칸, 2칸),

(1칸, 2칸, 1칸),

(2칸, 1칸, 1칸),

(2칸, 2칸)

의 방법으로 끝까지 도달할 수 있다.

가장 위의 1칸씩 뛰는 경우는 무시하고 볼 것이다.

 

위의 괄호들을 n칸이 들어가는 박스라고 생각할 때,

이 문제는 박스에서 2칸이 들어갈 수 있는 중복되지 않는 경우를 찾는 문제와 같다. -> combination

이 과정에서 박스의 총 길이가 1씩 줄어들고 2칸의 개수가 하나씩 늘어나는 형태이다.

반복해가면서 박스의 길이가 2칸의 개수와 같거나 작아지는 경우에 종료된다.

 

위 설명을 코드로 정리한다.

 

def combination(n, r):
    return factorial(n) // (factorial(r) * factorial(n-r))

\(n \choose r\)을 그대로 옮긴 코드

단순히 나누기를 하면 런타임에러(OverflowError)가 발생한다.

소수부가 너무 커지면서 발생하는 문제인 듯하다.

// 연산자를 사용해서 몫만을 반환하게 해주면 에러가 해결된다.

 

 

answer = 1

모두 1칸씩 뛰어 도달하는 경우는 계산하지 않는다.

 

i = 1
while i <= n-1:
	answer += combination(n-1, i)
	n -= 1
	i += 1

i는 2칸의 개수를 의미한다.

i가 n-1보다 커지면 반복을 종료한다.

 

n-1과 i의 조합을 계산하여 answer에 더한 뒤

n을 1 줄이고 i를 1 늘린다.

이후 반복

 

return answer % 1234567

구한 answer에서 1234567을 나눈 나머지를 반환해준다.