[Programmers] 멀리 뛰기 - JavaScript

Joosi_Cool·2023년 2월 9일
0

Programmers

목록 보기
14/98
post-thumbnail

문제설명



설계 과정

본인은 1의 개수와 2의 개수를 분리 시킨 다음에 이를 조합으로 생각했다.
1) 만약 1의 개수가 3개, 2의 개수가 5개라면 8개 중에 2가 들어갈 5개를 선택한다. 이 부분은 2가 들어가는 곳이라고 생각한다.
2) 이후로는 1 두개를 합쳐서 2 하나를 만들고, 이걸로 다시 조합에 넣었다.
-> ex) 1: 3개 / 2: 5개 = 8C5 => 1개 / 2: 6개 = 7C5
3) 결국, 1이 아예 1개, 0이 될때까지 이를 반복한다.



풀이 코드

function combination(n, r){
    var answer =1;
    if(n===r){
        return 1;
    }
      for(var i = n;i>(n-r);i--){
          answer = answer * i;
      }
      for(var i =r;i>0;i--){
          answer = answer /i;
      }
      return answer;
  }
  function solution(n) {
      var answer = 0;
      var one =n;
      var two = 0;
      while(true){
        if(one===1||one===0){
            answer+=combination(one+two,two);
            break;
        }
        answer+=combination(one+two,two);
        console.log(one,two,answer);
        one = one -2;
        two++;
      }
      return answer;
  }


결과

결과는 참담했다..... 내 풀이가 틀린건가??



새로운 설계

이번엔 순열이 아니라 점화식을 이용했다. 문제를 1부터 차례대로 한 4까지 구해보니, 문제가 점화식에 대한 것이란걸 눈치챘다. 이를 알자마자 1분만에 문제를 풀었다.
이 부분을 아냐 모르냐가 이 문제에 핵심인 것 같다.



해결 코드

  function solution(n) {
      var ansArr = [0,1,2];
      if(n<=2) return ansArr[n];
      for(var i =3;i<=n;i++){
          ansArr[i] = (ansArr[i-1] + ansArr[i-2])%1234567;
      }
      return ansArr[n];
  }


최종 결과

profile
집돌이 FE개발자의 노트

2개의 댓글

comment-user-thumbnail
2023년 2월 9일

헐 어려워보여요..

1개의 답글