[알고리즘]프로그래머스 12914번 - 멀리 뛰기

프로그래머스 12914번 - 멀리 뛰기

프로그래머스 12914번 - https://programmers.co.kr/learn/courses/30/lessons/12914

 

요구사항

1. 한 번에 1칸 또는 2칸을 뛸 수 있을 때, n개의 칸을 건너 끝에 도달하는 방법의 수를 1234567로 나눈 나머지를 반환하라.

 

요구사항 분석 및  풀이과정

1. n개의 칸을 건너 끝에 도달하는 방법의 수를 dp[n]이라고 정의하면 다음과 같습니다.

 

dp[n] = dp[n-2] + dp[n-1] ( n >= 3 )

 

dp[1] = 1 ( 1칸 )

dp[2] = 2 ( 1칸 + 1칸, 2칸 )

 

n개의 칸을 건너 끝에 도달하는 경우 마지막에 2칸을 뛰어 끝에 도달하는 경우와, 1칸을 뛰어 끝에 도달하는 경우가 있습니다.

 

마지막에 2칸을 뛰는 경우는 마지막 2칸을 제외한 n-2 개의 칸을 건너오는 경우의 수이고, 마지막에 1칸을 뛰는 경우는 마지막 1칸을 제외한 n-1 개의 칸을 건너오는 경우의 수이며 두 합이 n개의 칸을 건너 끝에 도달하는 방법의 수입니다.

 

소스코드 작성

class Solution {

	private static final int MOD = 1234567;

	private static long mod(long a, long b) {
		return ((a % MOD) + (b % MOD)) % MOD;
	}

	public long solution(int n) {
		if (n == 1) {
			return 1;
		}

		long[] dp = new long[n + 1];
		dp[1] = 1;
		dp[2] = 2;

		for (int i = 3; i <= n; i++) {
			dp[i] = mod(dp[i - 1], dp[i - 2]);
		}

		return dp[n];
	}
}

 

결과

 

소스코드 깃허브 주소

링크