문제
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12914
멀리 뛰기를 연습하는 효진이는 한 번에 1칸 또는 2칸을 뛸 수 있다. 예로 들어 칸이 4개라면 효진이는 (1칸, 1칸, 1칸, 1칸), (1칸, 2칸, 1칸), (1칸, 1칸, 2칸), (2칸, 1칸, 1칸), (2칸, 2칸)의 5가지 방법으로 맨 끝에 도달할 수 있다.
멀리뛰기에 사용될 칸의 수 N이 주어질 때 효진이가 끝에 도달하는 방법이 몇 가지인지 알아낸 후, 그 값을 1234567로 나눈 나머지를 반환하라.
같은 것이 있는 순열
이해하기 편하게 예시를 들어 설명한다.
\(a, b, c, d, e\) 를 일렬로 나열하는 방법의 수는 \(5!\)이 된다.
그렇다면 \(a, a, b, c, d\)를 일렬로 나열하는 방법을 생각해 보자. 먼저 \(a_1, a_2, b, c, d\)을 일렬로 배열한다고 생각하면 \(5!\)이 된다. 실제로 \(a_1, a_2\)는 동일하므로 두 요소를 배열하는 방법의 수인 \(2!\)을 나눠주어야 한다. 즉, \(\frac{5!}{2!}\)이 된다.
더 나아가 \(a, a, a, b, b, c\)를 일렬로 나열하는 방법을 생각해 보자. 6개의 숫자 중 a가 3개, b가 2개가 존재한다. 따라서 \(\frac{6!}{3!\cdot2!}\)이 일렬로 나열하는 방법의 수가 된다.
풀이
위의 같은 것이 있는 순열을 생각해보면 멀리 뛰기 문제는 1과 2로 이루어지고 총합이 n인 숫자들을 나열하는 방법의 수를 구하라는 것으로 해석할 수 있다. 따라서 2의 개수가 최대인 경우부터, 2 없이 1로만 이루어진 경우까지 1과 2를 나열하는 방법의 수를 합했다.
풀이는 다음과 같다.
1. 2의 개수가 최대일 때의 2의 개수와 1의 개수를 구한다.
twos = n // 2
ones = 0 if n % 2 == 0 else 1
2. 숫자 2와 1을 나열하는 방법의 개수를 구해 누적한다.
먼저 n이 짝수인 경우에는 2만 존재하므로 나열하는 방법의 수는 1이 된다.
그 외에는 같은 것이 있는 순열 공식을 적용한다. 숫자가 제법 크기 때문에 나누기 연산을 할 때는 int형 데이터를 유지할 수 있도록 주의한다.
if ones == 0:
answer += 1
else:
answer += math.factorial(twos + ones) // (math.factorial(twos) * math.factorial(ones))
3. 2의 개수와 1의 개수를 갱신한다.
2의 개수가 최대인 경우부터 시작했으므로, 2의 개수는 1개 줄고 1의 개수는 2개 늘어야 한다.
twos -= 1
ones += 2
4. 2~3번을 2의 개수가 0이 될 때까지 반복한다.
while twos >= 0:
if ones == 0:
answer += 1
else:
answer += math.factorial(twos + ones) // (math.factorial(twos) * math.factorial(ones))
twos -= 1
ones += 2
5. 결과값을 1234567로 나눈 나머지를 반환한다.
answer % 1234567
전체 코드는 접은글로 적어둔다.
import math
def solution(n):
twos = n // 2
ones = 0 if n % 2 == 0 else 1
answer = 0
while twos >= 0:
if ones == 0:
answer += 1
else:
answer += math.factorial(twos + ones) // (math.factorial(twos) * math.factorial(ones))
twos -= 1
ones += 2
return answer % 1234567
참고 문서
https://bhsmath.tistory.com/153