# 멀리 뛰기

## 1. 개요

* 프로그래머스
* Lv.2
* 연습문제
* [문제 바로가기](https://school.programmers.co.kr/learn/courses/30/lessons/12914)

***

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

***

### 2-1. 문제 설명 - 제한 사항

* n은 1 이상, 2000 이하인 정수입니다.

***

### 2-2. 문제 설명 - 입출력 예

| n | result |
| - | ------ |
| 4 | 5      |
| 3 | 3      |

***

### 2-3. 문제 설명 - 입출력 예 설명

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

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

***

## 3. 문제 풀이 1

```javascript
function solution(n) {
  // 1) n이 1, 2일 땐 각각 1과 2를 리턴하기
  if (n === 1) return 1;
  if (n === 2) return 2;
  // 2) 피보나치 수열의 첫 번째와 두 번째 값을 미리 정하기
  const arr = [1, 2];
  // 3) 반복문을 통해 n번째에 해당하는 값 구하기
  for (let i = 3; i <= n; i++) {
    const num = BigInt(arr[arr.length - 2]) + BigInt(arr[arr.length - 1]);
    arr.push(num);
  }
  // 4) 마지막 요소에 1234567를 나누었을 때 나오는 나머지를 리턴하기
  return arr.pop() % BigInt(1234567);
}
```

효진이가 `n` 칸을 뛸 수 있는 경우의 수는 `n-2` 칸 일 때의 경우의 수와 `n-1` 칸 일 때의 경우의 수를 합한 값이다. 즉, 피보나치 수열의 형태의 규칙을 갖는다. 그 이유는 아래의 설명을 참고하면 된다.

만약 효진이가 10칸을 뛰어야 한다.

* 8칸에서 뛰었던 모든 경우에서 2칸씩 더 뛰면 10칸이 된다.
* 9칸에서 뛰었던 모든 경우에서 1칸씩 더 뛰면 10칸이 된다.

그렇기 때문에 10칸을 뛸 수 있는 경우에 수는 `8칸에서 뛰었던 경우의 수 + 9칸에서 뛰었던 경우의 수` 가된다.

이를 바탕으로 피보나치 수열을 이용하여 문제를 풀었다.

***

### 1) n이 1, 2일 땐 각각 1과 2를 리턴하기

```javascript
if (n === 1) return 1;
if (n === 2) return 2;
```

`n`이 1과 2일 땐 1과 2를 각각 리턴한다.

***

### 2) 피보나치 수열의 첫 번째와 두 번째 값을 미리 정하기

```javascript
const arr = [1, 2];
```

이전전과 이전 값을 가지고 새로운 값을 만들어야 하기 때문에 첫 번째와 두 번째 값을 미리 정한다.

***

### 3) 반복문을 통해 n번째에 해당하는 값 구하기

```javascript
for (let i = 3; i <= n; i++) {
  const num = BigInt(arr[arr.length - 2]) + BigInt(arr[arr.length - 1]);
  arr.push(num);
}
```

`n`이 1과 2일 땐 위에서 리턴을 하였기 때문에 `n`이 3일 때 부터 계산을 하면 된다. 반복문을 통해 `arr` 배열의 마지막 값과 마지막 전 값을 더해 새로운 숫자를 만들고 이 숫자를 `arr` 배열에 마지막 요소로 넣는다.

이때 `BigInt`를 사용하는 이유는 `n`이 커지면 `arr` 배열에 저장하는 숫자의 값이 `int`의 범위보다 커지기 때문이다.

***

### 4) 마지막 요소에 1234567를 나누었을 때 나오는 나머지를 리턴하기

```javascript
return arr.pop() % BigInt(1234567);
```

`arr`의 마지막 요소는 `n`번째에 해당하는 숫자이다. 이를 `Array.pop()` 메서드를 통해 가져오고 문제의 조건에 맞게 `1234567`로 나누어 나온 나머지를 리턴한다.

`arr` 요소는 숫자이면 이 숫자는 `BigInt`이다. 그러므로 `1234567`도 `BigInt`로 바꾸어야 한다.

***

### 결과

![programmers\_run\_far\_result](/files/ZWmEThzUFGpKbTM79dW5)

***

## 4. 문제 풀이 2

```javascript
function solution(n) {
  if (n === 1) return 1;
  if (n === 2) return 2;
  function sum(a, b, i) {
    if (n === i) return (a + b) % BigInt(1234567);
    else return sum(b, a + b, ++i);
  }
  return sum(BigInt(1), BigInt(2), 3);
}
```

꼬리 재귀를 사용한 방법이다.

`n`이 1과 2일 땐 `문제 풀이 1`과 같다. 여기서는 `sum` 함수에 대해서만 설명한다.

`sum` 함수는 3개의 매개변수를 받는다.

* a: 이전전의 해당 하는 값
* b: 이전에 해당 하는 값
* i: 3부터 시작하며 `sum` 함수가 얼마만큼 호출되었는지 나타냄

`sum` 함수의 처음 호출은 아래에서 이루어진다.(아래 코드 참고)

```javascript
return sum(BigInt(1), BigInt(2), 3);
```

첫 번째 매개변수로는 1, 두 번째 매개변수로는 2, 그리고 마지막 매개변수로는 3을 호출한다. `sum` 함수가 실행하는 동시에 반환을 한다. 이렇게 해도 괜찮은 이유는 `sum` 함수 내에서도 조건에 따라 다시 `sum` 함수를 호출하기 때문이다.

만약 세 번째 매개변수와 `n`이 같다면 즉, 효진이가 뛰어야 하는 칸까지 뛰어야하 하는 경우의 수를 모두 구했다면 첫 번째 매개변수와 두 번째 매개변수를 더 한 값에 1234567를 나눈 값의 나머지를 리턴한다.

그렇지 않고 세 번째 매개변수와 `n`이 다르다면 다시 `sum` 함수를 호출하는데 이때 첫 번째 매개변수는 `b`가 되고 두 번째 매개변수는 `a + b`가 된다. 그리고 세 번째 매개변수는 i에 1을 더한 값이 된다.

이렇게 `i`가 `n`과 같아 질 때 까지 계속해서 `sum` 함수를 호출 리턴을 반복한다. 리를 꼬리 재귀 방법이라고 한다.

***

### 결과

![programmers\_run\_far\_resutl2](/files/oB4j7YPhwBVmvN4ditJ9)

***

## 5. Conclusion

> 해당 문제가 피보나치 수열이라는 것을 깨닫기 까지 많은 시간이 걸렸다. 피보나치 수열이라는 것을 알았다면 쉽게 문제를 풀 수 있었지만 그렇지 않고 조합을 바탕으로 문제를 풀려고 했다. 그렇기 때문에 시간 초과가 많이 발생하게 되었다. 많이 헤맨 문제이지만 그 만큼 이 문제를 풀면서 고민했던 내용이 나에게 큰 도움이 되었다. 또한 꼬리 재귀라는 개념을 사용할 수 있어 좋았다.

***

📅 2022-09-21


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://noah-dev.gitbook.io/til/coding-test/programmers/level2/programmers_run_far.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.