[프로그래머스] : 멀리뛰기

문제

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하면 됩니다.

 

입출력 예

 

입출력 예 설명

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

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

 

풀이

위 문제는 DP를 사용해서 해결할 수 있다.

먼저, 1과 2를 사용하여 합이 n이 되는 모든 경우의 수를 구하고

그 개수에서 1234567를 나눈 나머지를 반환하면 된다.

 

1. 1과 2를 사용하여 합이 n이 되는 모든 경우의 수 구하기

def count_combinations(n):
    dp = [0] * (n + 1)   # dp[i]는 합이 i가 되는 순열의 수
    dp[0] = 1            # 합이 0이 되는 방법은 "아무것도 선택하지 않기" 1가지

    for i in range(1, n + 1):           # i는 현재 만들고 싶은 목표 합
        for num in [1, 2]:              # num은 사용할 수 있는 숫자 (1 또는 2)
            if i - num >= 0:            # 음수가 되면 안 되니까 확인
                dp[i] += dp[i - num]    # 이전 경우에 num을 붙여서 현재 합 만들기

    return dp[n]  # 최종적으로 합이 n이 되는 경우의 수

이렇게 하면, 1과 2를 사용해 합이 n이 되는 경우의 수를 구할 수 있다.

 

2. 1234567에서 나눈 나머지

print(count_combinations(n) % 1234567)

이렇게 구한 개수에서 1234567을 나눈 나머지를 구하면 된다.

 

 

정답

def solution(n):
    return count_combinations(n) % 1234567

def count_combinations(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        for num in [1, 2]:
            if i - num >= 0:
                dp[i] += dp[i - num]
    return dp[n]

 

DP 알고리즘이 궁금하다면 아래 글을 참고해주세요.

https://haram22.tistory.com/95