[프로그래머스] 멀리 뛰기 (LV2 - JavaScript)

프로그래머스

 

1. 문제

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

2. 오답

풀이 전략

• 중복이 있는 순열 공식 활용 (1칸: a, 2칸: b)
• n! / (a! * b!)

// num을 인자로 받아 num 팩토리얼을 리턴(num이 0이면 0! = 1)
const factorial = (num) => {
    let result = 1;
    if (num < 1) return result;
    
    for (let i=1; i<=num; i++) {
        result *= i;
    }
    return result;
}

function solution(n) {
    const arr = [];
    let result = 0;
    
    // 건널 수 있는 경우의 수를 arr에 push ([2칸, 1칸] 형태)
    for(let i=0; i<=n/2; i++) {
        arr.push([i, n - 2 * i])
    }
    
    arr.forEach(([two, one]) => {
        let totalFactorial = factorial(two + one);
        let twoFactorial = factorial(two);
        let oneFactorial = factorial(one);
        
        result += (totalFactorial) / (twoFactorial * oneFactorial); // 중복 순열 공식 적용
    })
    
    return result % 1234567;
}

 

문제 7번부터 탈락.. 찾아보니 n이 커지면서 숫자가 너무 커져 다른 값이 연산되거나 infinity인 경우가 존재한다.

메모장에 1칸부터 순서대로 적다 보니 피보나치 수열이 보였다...🤣🤣🤣

 

3. 정답 풀이

풀이 전략

• 피보나치 수열이용

function solution(n) {
	// 피보나치 수열 (n[i] = n[i-1] + n[i-2])
    const result = (num) => {
        const arr = new Array(num).fill(0);
        for(let i=0; i<n; i++) {
        	// 피보나치 수열 연산을 위해 1칸 가는 경우 임의로 추가
            if (i === 0) arr[i] = 1;
            // 피보나치 수열 연산을 위해 2칸 가는 경우의 수 임의로 추가
            else if (i === 1) arr[i] = 2;
            // 숫자가 너무 커져 잘못된 연산 결과나 infinity를 리턴하는 것을 막기 위해 몫 연산(%1234567)을 매번 시행
            else arr[i] = (arr[i-1] + arr[i-2]) % 1234567;
        }
        return arr[num-1];
    }
    return result(n)
}

 

 

 

느낀 점

• 알고리즘 풀기 전에 테스트 케이스 직접 풀어보고 추가해보는 습관을 가져야겠다.
• 알고리즘 풀이에 사용했던 공식들 까먹지 말고 기억해놔야겠다.
• 연산의 결과가 너무 커져서 잘못된 연산 결과나 infinity가 나오는 경우는 생각도 못했다... 다음 문제부터는 연산 결과 고려해야겠다.

 

 

[프로그래머스] 구명보트 (LV2 - JavaScript)

 

[프로그래머스] N개의 최소공배수 (LV2 - JavaScript)