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

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를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한 사항

• n은 1 이상, 2000 이하인 정수입니다.

입출력 예nresult

4	5
3	3

입출력 예 설명

입출력 예 #1
위에서 설명한 내용과 같습니다.

입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

 

문제 이해

- n칸을 뛸 때, 1칸/2칸으로 뛰는 경우의 수를 찾는 문제입니다.

- 처음에 시도할 때 순열 생성 후 완전탐색을 통해 해결하였으나, 시간초과가 발생하였습니다.

- 이후 다이나믹 프로그래밍을 이용하여 해결하였습니다.

 

문제 풀이(순열-시간초과)

- 짝수일 때와 홀수일 때를 나눠서 순열을 통해 모든 경우의 수를 탐색하는 내용입니다.

- n을 2로 나눈 갯수(i)를 기준으로 반복문을 돌고, 짝수면 0일 경우와 i가 최대(n//2)일 때만 1개이고, 홀수일 경우 0일때만 항상 1개의 경우의 수를 갖습니다.

- 이외의 경우는 순열을 생성해서 탐색합니다. 1*n으로 이루어진 배열에서 2의 갯수(i)에 따라 배열을 2가 들어가도록 수정합니다. 이후 숫자의 갯수만큼 순열을 생성한 후 중복을 제거하기 위해 집합으로 만들어줍니다.

- 해당 코드는 시간초과가 발생합니다.

 

코드

#프로그래머스 12914 멀리 뛰기

from itertools import permutations

from collections import deque

def solution(n):

    answer = 0

    if n%2==0: #even

        for i in range((n//2)+1):

            if i==0 or i==(n//2):

                answer += 1

            else:

                arr = deque([1]*n)

                for j in range(i):

                    arr.popleft()

                    arr.popleft()

                    arr.append(2)

                answer += len(set(permutations(arr,n-i)))

    else: #odd

        for i in range((n//2)+1):

            if i==0:

                answer += 1

            else:

                arr = deque([1]*n)

                for j in range(i):

                    arr.popleft()

                    arr.popleft()

                    arr.append(2)

                answer += len(set(permutations(arr,n-i)))

    return answer%1234567

 

문제 풀이(다이나믹 프로그래밍)

- 시간초과가 발생하는 것을 보고 시간복잡도로 인해 다이나믹 프로그래밍을 시도해야겠다고 생각했습니다.

- n의 갯수에 따라 만들어지는 조합들을 나열해보면 규칙성을 찾을 수 있습니다. 해당 규칙은 피보나치 수(n = n-1 + n-2)만큼 늘어납니다.

- 또한 아래 그림과 같이 실제 n일때의 조합들도 모두 피보나치 규칙을 따르는 것을 확인할 수 있습니다.

- 이에 따라 2000(입력)+1개의 dp배열을 생성한 후 n에 따른 값을 넣어줍니다.

- 이후 반복문을 도리며 dp[i]번째를 생성해줍니다.

 

 

코드

#프로그래머스 12914 멀리 뛰기

def solution(n):

    dp = [0]*2001

    dp[0] = 1

    dp[1] = 1

    dp[2] = 2

    for i in range(2,n+1):

        dp[i] = dp[i-2] + dp[i-1]

    return dp[n]%1234567

print(solution(4))

print(solution(3))