[Programmers][Python] 멀리 뛰기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

 

처음 작성한 코드

경우의 수를 계산한 풀이

• n개의 종류의 요소 {a1, a2, ..., an} 가 합쳐서 m개가 있을 때 나올 수 있는 경우의 수는 m! / (a1! * a2! * ... * an!)가 된다.
  • 이 문제에서는 1번 뛰기와 2번 뛰기만 존재하므로 요소는 {a1, a2} 두 개만 고려하면 된다.
  • 2번 뛰기 요소가 하나 늘어날 수록 1번 뛰기 요소의 개수가 하나씩 줄어들게 된다.
  • 2번 뛰기의 요소가 i개 일 때 1번 뛰기의 요소는 n - i*2 개가 된다.
  • 따라서 경우의 수는 (n - i)! / ((n - i*2) * i)가 된다.
• 루프문을 이용해 2번 뛰기의 요소가 0개부터 n//2 개까지 경우를 모두 더하면 된다.

from math import factorial

def solution(n):
    answer = 0
    for i in range(0, n//2 + 1):
        answer += factorial(n - i) // (factorial(n - i*2) * factorial(i))
    return answer % 1234567

# 입출력 예시
print(solution(4))
print(solution(3))

 

 

물론 아래와 같이 일부 곱셈 연산을 상쇄시켜서 계산할 수 있다.

def fac(a, b):
    alu = 1
    for i in range(a, b + 1):
        alu *= i
    return alu

def solution(n):
    answer = 0
    for i in range(0, n//2 + 1):
        answer += fac(n - i*2 + 1, n - i) // fac(1, i)
    return answer % 1234567

문제의 요점은 사실 이게 아니라 아래의 피보나치수열을 이용한 풀이를 물어보는 문제이다.

 

다른 코드

[코드1]

피보나치 수열을 이용한 풀이

• 기본적인 피보나치 수열이다.

def solution(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a+b
    return b

피보나치 수열이 적용되는 이유는 n+2 번째의 경우에서는 아래의  n 번째의 경우와 n+1 번째의 경우가 적용되기 때문이다.

n+2 번째의 경우 = (n 번째의 경우 + [2 번 뛰기]) + (n+1 번째의 경우 + [1 번 뛰기])

 

예를 들면,

1 번째의 경우: [(1)]

 

2 번째의 경우: [(1, 1), (2)]

 

3 번째의 경우:

1 번째의 경우 + (2 번 뛰기), 2 번째의 경우 + (1 번 뛰기)

=> [(1)] + (2번 뛰기), [(1, 1), (2)] + (1 번 뛰기)

=> [(1, 2), (1, 1, 1), (2, 1)]

 

4 번째의 경우:

2 번째의 경우 + (2 번 뛰기), 3 번째의 경우 + (1 번 뛰기)

=> [(1, 1), (2)] + (2 번 뛰기), [(1, 2), (1, 1, 1), (2, 1)] + (1 번 뛰기)

=> [(1, 1, 2), (2, 2), (1, 2, 1), (1, 1, 1, 1), (2, 1, 1)]

처럼 적용 된다.