[백준] 2553번. 마지막 팩토리얼 수(JAVA)

문제

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

---

풀이(35분)

import java.io.*;

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());
        int[] dp = new int[20001]; // 초기 배열 값을 위한 20001 초기화

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 6;
        dp[4] = 4; // 2의 제곱수까지의 값 저장

        int temp = 0;
        for (int i = 5; i <= n; i++) {
            if (i % 5 == 0) {
                temp = i / 5;
                dp[i] = (dp[temp] * (int) Math.pow(2, temp % 4)) % 10;
            } else {
                temp = (i / 5) * 5;
                dp[i] = dp[temp];
                for (int j = temp + 1; j <= i; j++) {
                    dp[i] = dp[i] * j % 10;
                }
            }
        }

        System.out.println(dp[n]);
    }
}

 

생각보다 복잡한 풀이를 했던 것 같다.

문제 풀이 초반 마지막 자릿수들만을 추적하며 지속적으로 값을 곱해나가면 되는 문제인줄 알았다.

 

예를 들면 이런 식이었다.

1은 1
2는 2
3은 6
4는 4
5는 2
6은 2
7은 4
8은 2
9는 8
10은 8
11은 8
12는 6
13은 8

하지만 계산을 해본 결과 25에서 4가 나와야 하는 것이 3이 나오는 오류가 있었다.

 

따라서, 처음에 문제 풀이를 생각한 대로 2와 5의 개수를 찾아 제거해주는 방식으로 진행하였다.