You Nicholas

가고 가고 또 가면 알게되고, 행하고 행하고 또 행하게 되면 이루게 된다.

1 분 소요

1. 문제

[level 2] 멀리 뛰기 - 12914

문제 링크

성능 요약

메모리: 10.2 MB, 시간: 0.60 ms

구분

코딩테스트 연습 > 연습문제

채점결과


정확성: 100.0
합계: 100.0 / 100.0

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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가지 방법으로 멀리 뛸 수 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

2. 해결방법 시간복잡도

  1. 단순 코딩 O(N)
  2. 더 쉽게 O(N)

3. 문제 해결 및 코드

  • 주석을 참고하면서 이해를 돕습니다.

4. 알고리즘 및 해설

  1. 피보나치 수열과 비슷한 방식으로 접근할 수 있다.
  2. 예시에서 제시한 대로 3까지는 경우의 수가 (2, 1), (1, 1, 1), (1, 2) 이렇게 3가지이고 이하도 마찬가지로 2개 1개이다. 그러므로 3 이상일때의 공식을 구하면 된다.
  3. 피보나치 수열과 비슷하므로 1과 2는 미리 값을 정한 뒤에 3부터 해당 숫자까지 반복문을 통해 해당 숫자 - 1까지의 경우의 수와 해당 숫자 - 2 까지의 경우를 수로 업데이트해준다.
  4. 이후 문제에서 제시한 1234567로 나누어서 결과값을 출력한다.
    • 이때 3보다 작은 경우는 그냥 n값으로 반환해준다.

5. 더 쉽게

def solution(n):
    a, b = 1, 2
    for i in range(2, n):
        a, b = b, a + b
    return b % 1234567
  1. 위와 같이 피보나치 수열이라고 접근하였을 때, 이전 피보나치 수라는 문제에서 접근했던 방식과 동일하게 멀티플 방식으로 해결이 가능하다.
    • 피보나치 수열의 경우, 풀이 방법이 대개 7가지 정도가 있는데 이와 같은 반복문으로도 간단하게 해결이 가능하다.

참고