프로그래머스 #12914. 멀리뛰기: DP/ lv2

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

참고

https://subinze.tistory.com/159

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

1차 - Backtracking을 활용한 중복 순열 문제 → 시간 초과

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

🚩제출한 코드

"""
문제 : N개 칸을 멀리뛰기하는 방법수 
출력 : 총 경우의 수 %123456
# 총 경우의 수 = 1,2 중 하나 시바 수중 중복 순열(순서o) 경우의 수 구학
# Backtracking

"""
answer = 0
def solution(n):
    
    def backtracking(path,lv):
        # 재귀 종료
        global answer
        if lv >= len(path):
            if sum(path)==n : 
                answer += 1 
            # print(f"{lv} : {path} >{answer}")
            return 0
        #자식 노드 이동 
        for x in [1,2] :
            if sum(path) + x <= n : 
                path[lv] = x 
                backtracking(path , lv+1)
            # backtracking
            path[lv] = 0 
            
    for m in range(1,n+1) :
        backtracking([0]*m , 0)
    return answer%1234567

• 💥 1차 제출