백준 1437번: 수 분해

음이 아닌 정수를 음이 아닌 정수들의 덧셈으로 분해한 후 전부 곱한 값의 최댓값을 구하는 문제이다.

 

0부터 4 까지는 현재 숫자와 분해한 수의 곱 최댓값이 같다.

if (n <= 4) {
    System.out.print(n);
    return;
}

 

 

5부터는 분해의 곱이 3의 배수일 때 최대가 되므로 현재 위치 - 3 의 값에 3을 곱한 값이 최댓값이 된다.

int[] board = new int[n + 1];
for (int i = 1; i <= 4; i++) {
    board[i] = i;
}
for (int i = 5; i <= n; i++) {
    board[i] = (board[i - 3] * 3) % mod;
}

 

 

결과 코드는 다음과 같다.

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

public class 수분해1437 {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int mod = 10_007;
        br.close();
        if (n <= 4) {
            System.out.print(n);
            return;
        }
        int[] board = new int[n + 1];
        for (int i = 1; i <= 4; i++) {
            board[i] = i;
        }
        for (int i = 5; i <= n; i++) {
            board[i] = (board[i - 3] * 3) % mod;
        }
        System.out.print(board[n]);
    }
    
}