[Python] 파이썬 프로그래머스 멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

---

나의 풀이

1. 처음엔 조합 solution으로 접근함

• 2를 최대로 쓰는 값을 구하고 (ex n = 7 , (2, 2, 2, 1)) 2를 1 두개로 변환하여 이에 대한 조합을 구함

from itertools import permutations
def solution(n):
    bin_n = bin(n)[2:]
    cnt_2 = 0
    cnt_1 = 0
    ans = 0

    if bin_n[-1] == '1':
        cnt_1 = 1
    for i in enumerate(bin_n[::-1]):
        if i[1] == "1":
            cnt_2 += 2**i[0]//2

    list_2 = [2 for _ in range(cnt_2)]
    list_1 = [1 for _ in range(cnt_1)]

    while cnt_2 >= 0 :
        list_2.extend(list_1)
        ans += len(set(permutations(list_2, len(list_2))))

        cnt_2 -= 1
        cnt_1 += 2
        del list_2[0]
        list_1.extend([1, 1])
    return ans % 1234567

---

2. DP를 생각해내고 재귀용법으로 접근함

• n칸을 뛰기 위해서는 n-2 칸에서 2칸, n-1칸에서 1칸 뛴것과 같음
• 시간초과 발생, 재귀용법을 사용하면 n-1번 n-2번 호출하기 때문에 오래 걸린다고 판단 \( O(n^{2}) \)

def solution(n):
    if n == 1 :
        return 1
    elif n == 2:
        return 2
    else:
        return solution(n - 1) + solution(n - 2) % 1234567

---

최종 코드

def solution(n):
    if n < 2:
        return n

    ans = [1, 2]
    for _ in range(n-2):
        ans.append(ans[-1]+ans[-2])

    return ans[-1] % 1234567

---

다른 사람의 풀이

• 다들 DP를 활용한 재귀용법과 순차순열을 사용하여 풀었음