멀리 뛰기

[문제 Link] https://programmers.co.kr/learn/courses/30/lessons/12914

문제 설명

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

로직

다이나믹 프로그래밍을 이용하여 풀었다. dp 배열을 만든 후에 0번째부터 n=1일 경우부터 시작한다.

만약 1칸일 경우 1번 점프하면된다.

2칸일 경우에는 2, 1-1 두가지 방법이 있다.

3칸일 경우 1-1-1, 2-1,1-2 3가지 경우가 있다.

4칸일 경우 1-1-1-1,1-2-1,1-1-2,2-1-1,2-2 5가지 방법이 있다.

이 때 규칙이 생기게 되는데 dp[n] = dp[n-1] + dp[n-2] 의 규칙이 생긴다.

dp 배열에 저장한 후 리턴해주면 된다.

전체 코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

class Solution
{
    public static long solution(int n) {

        int[] dp = new int[2000];
        dp[0] = 1;
        dp[1] = 2;
        
        if (n==1) 
            return 1;
        else if (n==2)
            return 2;

        for(int i=2;i<n;i++) 
            dp[i] = (dp[i-2] + dp[i-1]) % 1234567;

        return dp[n-1];
    }


    public static void Main(string[] args)
    {
        int n = 4;
        Console.WriteLine(solution(n));
    }
}

멀리 뛰기 [프로그래머스](C#)