[프로그래머스] 멀리 뛰기

 

안녕하세요 코밑이에염!

재미난 코테 문제를 풀어왔어요!

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

바로 멀리 뛰기입니다~

 

멀리 뛰기는 dp를 사용해서 푸는 문제에요~

dp는 다음에 자세히 포스팅 하도록 할게요~

 

문제 먼저 설명하겠습니다

 

효진이는 한번에 1칸 or 2칸을 뛸수 있음

뛰는 방법은 5가지가 나옴

(1, 1, 1, 1)

(1, 2, 1)

(1, 1, 2)

(2, 1, 1)

(2, 2)

 

4가 아닌 n번째까지 뛸 때의 방법

 

1 → 1번

1

 

2 → 2번

1, 1

2

 

3 → 3번

1, 1, 1

2, 1

1, 2

 

4 → 5번

1, 1, 1, 1

2, 1, 1

1, 2, 1

1, 1, 2

2, 2

 

5 → 8번

1, 1, 1, 1, 1

2, 1, 1, 1

1, 2, 1, 1

1, 1, 2, 1

1, 1, 1, 2

2, 2, 1

2, 1, 2

1, 2, 2

 

자 패턴을 알아내셨나요?

f(n) = f(n - 1) + f(n-2)

 

예로 n이 2인 경우와 n이 3인 경우는 각 각 방법이

2가지 3가지입니다

 

그런데 이제 n이 4인 경우는 방법이

5가지에요!!!

이런 간단한 패턴을 숨기고 있었답니다~

 

그럼 코드 보시겠습니다~

 class Solution {
        public long solution(int n) {
            long[] dp = new long[n + 1];

            dp[1] = 1;
            if (n != 1) { //넣지 않으면 n이 1일 때 터져버림
                dp[2] = 2;
            }

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

이렇게 간단하게 풀어보았어요~

 

오늘은 짤막하게 써보았어요~

 

그럼 안녕~