풀이 방법
2
dp[2] = dp[2] + dp[2-2]; // 0 + 1
dp[3] = dp[3] + dp[3-2]; // 0 + 0
dp[4] = dp[4] + dp[4-2]; // 0 + 1
dp[5] = dp[5] + dp[5-2]; // 0 + 0
dp[6] = dp[6] + dp[6-2]; // 0 + 1
dp[7] = dp[7] + dp[7-2]; // 0 + 0
dp[8] = dp[8] + dp[8-2]; // 0 + 1
3
dp[3] = dp[3] + dp[3-3]; // 0 + 1
dp[4] = dp[4] + dp[4-3]; // 1 + 0
dp[5] = dp[5] + dp[5-3]; // 0 + 1
dp[6] = dp[6] + dp[6-3]; // 1 + 1
dp[7] = dp[7] + dp[7-3]; // 0 + 1
dp[8] = dp[8] + dp[8-3]; // 1 + 1
5
dp[5] = dp[5] + dp[5-5]; // 1 + 1
dp[6] = dp[6] + dp[6-5]; // 2 + 0
dp[7] = dp[7] + dp[7-5]; // 1 + 1
dp[8] = dp[8] + dp[8-5]; // 2 + 1
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int N;
static boolean[] infinite;
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[N + 1];
infinite = new boolean[N + 1];
for (int i = 2; i <= N; i++) {
if (!infinite[i]) {
int x = 2 * i;
while (x <= N) {
infinite[x] = true;
x += i;
}
}
}
dp[0] = 1;
for (int i = 2; i <= N; i++) {
if (!infinite[i]) {
for (int j = i; j <= N; j++) {
dp[j] = (dp[j] + dp[j - i]) % 123456789;
}
}
}
System.out.println(dp[N]);
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
회문 - 17609번 (0) | 2021.12.30 |
---|---|
해킹 -10282번 (0) | 2021.12.29 |
줄세우기 - 2631번 (0) | 2021.12.28 |
그대, 그머가 되어 - 14496번 (0) | 2021.12.27 |
악덕 영주 혜유 (0) | 2021.12.24 |