Github

멀리 뛰기

1. 개요

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

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를 리턴하기

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

n이 1과 2일 땐 1과 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);
}

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

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

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

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

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

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

결과

4. 문제 풀이 2

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 함수의 처음 호출은 아래에서 이루어진다.(아래 코드 참고)

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 함수를 호출 리턴을 반복한다. 리를 꼬리 재귀 방법이라고 한다.

결과

5. Conclusion

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

📅 2022-09-21

Previous주차 요금 계산Next영어 끝말잇기

Last updated