2022/05/10) 2. 돌다리건너기 [Dynamic programming(동적계획법)]

1. 문제

<돌다리건너기>
: 철수는 학교에 가는데 개울을 만났다. 개울은 N개의 돌로 다리를 만들어 놓았다. 철수는 돌다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있다. 철수가 개울을 건너는 방법은 몇 가지일까?

2. 해결 방법

1. 앞에서 배운 계단오르기문제랑 동일하다. 다만 계단오르기는 N계단까지 가면 됐었고(N이 도착지), 현재 문제는 N개의 돌로 이뤄진 돌다리를 건너야 해서 N+1까지 가야한다. (N+1이 도착지) 도착지가 어딘지 잘 파악하자!

Q. 만약 한 번에 한 칸/두 칸/세 칸씩 건너뛸 수 있다면, 이럴 경우엔 어떻게 풀어야 할까?

• dy[3]까지 초기화를 해주어야 한다. dy[1], dy[2], dy[3]!
• 그렇다면 dy[3]에는 어떤 값이 들어갈까? dy[1]+dy[2]+1! 이다. 출발점에서 바로 세 칸해서 세 번째 돌다리에 도착할 수도 있으니까!
  그러므로 이렇게 해서, 다음 돌다리(dy[n])의 경우의 수를 구할 땐, dy[n-1]+dy[n-2]+dy[n-3]을 해주면 된다.

3. 정답

        <script>
            function solution(n){  
                let answer=0;
                let dy=Array.from({length:n+2}, ()=>0);
                dy[1]=1;
                dy[2]=2;
                for(let i=3; i<=n+1; i++){
                    dy[i]=dy[i-2]+dy[i-1];
                }
                answer=dy[n+1];
                return answer;
            }
            console.log(solution(7));
        </script>

4. 내 코드와 비교 그리고 반성

dy.length-1 이런 식으로 접근해서 좀 헷갈렸다.

      <script>
          function solution(n){  
              let answer = 0;
              let dy = Array.from({length:n+2}, ()=>0); //9 8.
              dy[1] = 1;
              dy[2] = 2;
              for(let n = 3; n <= dy.length-1; n ++){ //3, 4, 
                  dy[n] = dy[n-1] + dy[n-2];
              }
              answer = dy[dy.length-1];
              return answer;                
          }   
          console.log(solution(7));
      </script>