[레벨2] 멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

 

처음에는 1, 2를 사용해 리스트(배열)의 합이 n이 되는 모든 경우의 수를 찾는 것이라는 개념에서부터 출발했다. 그래서 작성한 코드는 아래와 같다.

# Python
from itertools import product


def solution(n):
    numbers = [1, 2]  # 사용할 숫자 리스트
    target_sum = n  # 목표 합

    result_list = []

    # 1 또는 2가 들어가서 합이 n이 되는 모든 조합 찾기
    for r in range(1, target_sum + 1):
        for case in product(numbers, repeat=r):
            if sum(case) == target_sum:
                result_list.append(list(case))

    return len(result_list) % 1234567

 

위 코드로 테스트 케이스는 문제없이 통과했는데 제출하니 시간 초과가 발생했다. 좀 더 고민해 보니 DP 알고리즘에 관한 문제였고 피보나치수열과 같은 방식으로 풀이하여 통과할 수 있었다. 파이썬 코드와, 자바스크립트 코드는 각각 아래와 같다.

# Python
def solution(n):
    if n == 1:
        return n

    a, b = 1, 2

    for _ in range(n-2):
        a, b = b, (a+b) % 1234567

    return b

 

// Javascript
function solution(n) {
  if (n == 1) return n;

  let a = 1;
  let b = 2;

  for (const _ of Array.from({ length: n - 2 }, (_, i) => i)) {
    temp = a;
    a = b;
    b = (temp + b) % 1234567;
  }

  return b;
}