백준 8394: 악수 [JAVA]

[문제 링크]

https://www.acmicpc.net/problem/8394

[난이도]

- Silver 3

 

[알고리즘]

- DP

 

[코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        long[] dp = new long[n + 1];

        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 2] + dp[i - 1]) % 10;
        }
        System.out.println(dp[n]);


        /**
         * dp[1] = 1
         * dp[2] = 2
         * dp[3] = 3
         * dp[4] = 5
         * dp[5] = 8
         * 피보나치 수열임
         */

    }
}

[풀이]

피보나치 수열의 마지막 자리 숫자만 출력하는 문제이다. 수를 10으로 나눈 나머지의 값이 마지막 숫자이다.