문제 풀이(47)

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

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


public class Main {

    static int N;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        dp = new int[5000 + 1];

        dp[1] = -1;
        dp[2] = -1;
        dp[3] = 1;
        dp[4] = -1;
        dp[5] = 1;

        for (int i = 6; i <= N; i++) {

            if ( (i-5)% 3 == 0 || (i-3) % 5 == 0) {
                dp[i] = Math.min(dp[i-3] + 1, dp[i-5] + 1);
              
                continue;
            }
         
            if (i % 3 == 0 && i % 5 != 0) {
                dp[i] = dp[i-3] + 1;
              
                continue;
            }
            if (i % 3 != 0 && i % 5 == 0) {
                dp[i] = dp[i-5] + 1;
               
                continue;
            }
            if (i % 3 == 0 && i % 5 == 0) {
                dp[i] = Math.min(dp[i-3] + 1, dp[i-5] + 1);
              
                continue;
            }

            if (dp[i-5] != -1 || dp[i-3] != -1) {
                dp[i] = Math.min(dp[i-5] + 1, dp[i-3] + 1);
              
                continue;
            }

            dp[i] = -1;
        }

     

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