[프로그래머스] 12914. 멀리 뛰기 & 12945. 피보나치 수

사용 언어: 파이썬(Python)

 

 

12914. 멀리 뛰기(LV. 2)

프로그래머스

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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	return
4	5
3	3

 

풀이

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

 

풀이 설명

재귀나 반복으로도 해당 문제를 풀 수 있겠지만, 동적계획법(DP, Dynamic Programming)을 이용하면 비교적 간단하게 풀 수 있는 문제다.

n칸 까지 멀리 뛰기를 하는데 걸리는 횟수를 F(n)이라고 정의한다면, F(n)까지 도달하는 방법은

   [1] (n-1)자리에서 1칸을 뛰어 오거나

   [2] (n-2)자리에서 2칸을 뛰어 오거나

이 두 가지 경우 밖에 없다.

 

그렇기 때문에 n까지 도달하는데 걸리는 횟수는"F(n) = F(n-2) + F(n-1)"와 같이 표현할 수 있다.

 

예를 들어 n=2라면 F(2) = 2이다.

* 거리 2까지 도달하는 위해서는 0번째 칸으로부터 2칸 뛰기를 해서 오거나, 1번째 칸으로 부터 1칸을 뛰어오는 방법이 가능하므로 2가지 경우를 가진다.

 

n까지 경우의 수를 계산하기 위해 순서에 따른 경우를 기록할 테이블 case = [1, 1]을 만들고, 거리 n까지 경우를 구하기 위해 반복문을 통해 앞에서 부터 각 경우의 수를 계산하였다.

* F(1) = 1 (거리 1까지 도달하기 위해서는 1칸 뛰기만 가능하다)

* F(0) = 1 (거리 0까지 도달하는 방법을 1이라고 임의적으로 정의했다)

 

→ case = [1, 1, 2, 3(=1+2), 5(=2+3), ... , k(= case[n-1] + case[n-2])]

 

해당 방식은 피보나치 수열을 구하는 방식과도 동일하다. 

 

 

 

12945. 피보나치 수(LV. 2)

프로그래머스

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

 

제한 사항

n은 2 이상 100,000 이하인 자연수입니다.

 

입출력 예시

n	return
3	2
5	5

 

풀이

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

 

풀이 설명

위와 같으므로 생략.