[백준 8394 JAVA] 악수

 

 

해당 케이스들의 답을 적어놓으면서 풀면 쉽게 풀리는 문제

점화식이 피보나치 수열의 패턴을 따라가는 것을 볼 수 있다.

원리를 추측하자면
Dp[n]에서 처음 두명이 악수를 하는 경우 : Dp[n-2]

DP[n]에서 처음 두명이 악수를 안하는 경우 : Dp[n-1]

따라서 Dp[n] = Dp[n-1]+Dp[n-2]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main{

    /*
    1 = 1
    2 = 2
    3 = 3
    4 = 5
    5 = 8
     => 피보나치 수열이다

     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int dp[] = new int[N+1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3 ; i<=N; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 10;
        }
        System.out.println(dp[N]);

    }
}