프로그래머스|멀리 뛰기

문제 설명

1과 2를 사용해서 n을 만드는 방법의 개수를 출력하는 문제입니다. 단 수가 너무 커지는 것을 방지하기 위해 1234567로 나눈 나머지를 출력합니다.

작동 순서

1. n을 입력받고 1부터 n까지 만들 수 있는 경우의 수를 저장할 dp 배열을 생성해줍니다. 만약 n이 1인 경우 그냥 1을 출력하고 프로그램을 종료합니다.
2. n이 1일 때는 1을 사용해서 만드는 방법 한 가지, n이 2일 때는 1, 1과 2 이렇게 두 가지 방법이 있으므로 dp[1]=1, dp[2]=2로 저장해줍니다.
3. n이 3 이상일 때는 만드는 방법이 n-1에 1을 더해주는 방법, n-2에 2를 더해주는 방법이 있으므로 n-1을 만드는 경우의 수와 n-2를 만드는 경우의 수를 더해줍니다.
4. n까지 계산을 완료하면 n을 만드는 경우의 수를 출력해줍니다.

소스코드

def solution(n):
    if n==1:
        return 1
    dp = [0 for i in range(n+1)]
    dp[1]=1
    dp[2]=2
    for i in range(3,n+1):
        dp[i]=dp[i-1]%1234567+dp[i-2]%1234567
        dp[i]%=1234567
    return dp[n]