[99클럽 코테 스터디 22일차 TIL] 멀리 뛰기

💡문제

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 이하인 정수입니다.

입출력 예

n	result
4	5
3	3

입출력 예 설명

입출력 예 #1

위에서 설명한 내용과 같습니다.

입출력 예 #2

(2칸, 1칸)

(1칸, 2칸)

(1칸, 1칸, 1칸)

총 3가지 방법으로 멀리 뛸 수 있습니다.

 

💡키워드

• 동적계획법

 

💡접근/해결 방법

문제에서 n은 1이상 2000이하의 정수라고 되어있다. n이 1일때 부터 하나씩 생각해보자.

n = 1 이면, (1칸) → 1가지

n = 2 이면, (1칸, 1칸), (2칸) → 2가지

n = 3 이면, (1칸, 1칸, 1칸), (1칸, 2칸), (2칸, 1칸) → 3가지

n = 4 이면, (1칸, 1칸, 1칸, 1칸), (1칸, 2칸, 1칸), (1칸, 1칸, 2칸), (2칸, 1칸, 1칸), (2칸, 2칸) → 5가지

n = 5 이면, (1칸, 1칸, 1칸, 1칸, 1칸), (1칸, 1칸, 1칸 2칸), (1칸, 1칸, 2칸, 1칸), (1칸, 2칸, 1칸, 1칸), (2칸, 1칸, 1칸, 1칸), (1칸, 2칸, 2칸), (2칸, 1칸, 2칸), (2칸, 2칸, 1칸) →8가지

…

하나씩 파악해보면 결국 피보나치 수열 문제라는 것을 알 수 있다.

따라서 다음과 같이 풀 수 있다. 문제에서 n=2이면 2이고, n은 1이상이라는 점을 고려해야한다.

 

✅ 풀이1

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

 

✅ 풀이2

def solution(n):
    answer = 0
    a, b = 0,1
    
    for i in range(n) :
        a,b = b, a+b
    
    answer = b % 1234567
    return answer