> For the complete documentation index, see [llms.txt](https://noah-dev.gitbook.io/til/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://noah-dev.gitbook.io/til/coding-test/programmers/level2/programmers_run_far.md).

# 멀리 뛰기

## 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