https://www.acmicpc.net/problem/14650
저는 DP를 이용해 문제를 해결했습니다.
먼저 3의 배수는 각 자리수의 합이 3의 배수인 경우입니다. 그래서 저는 합을 구하면서 진행했습니다.
DP를 통해 해당 뎁스와 합에 대한 경우의 수를 저장했습니다.
package BOJ.dp;
import java.awt.print.Pageable;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.function.Function;
public class BOJ_14650 {
private static final int NOT_VALID = -1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Function<String,Integer> stoi = Integer::parseInt;
int n = stoi.apply(br.readLine());
int[][] dp = new int[n][2*9+1];
for(int i = 0 ; i < n ; i++){
Arrays.fill(dp[i],NOT_VALID);
}
int result = cal(0,0,n,dp);
System.out.println(result);
}
private static int cal(int depth, int sum, int n,int[][] dp) {
if(depth == n){
if(sum % 3 == 0){
return 1;
}else{
return 0;
}
}
if(dp[depth][sum] != NOT_VALID) {
return dp[depth][sum];
}
int result = 0;
for(int i = 0 ; i < 3; i++){
if(depth == 0 && i == 0){
continue;
}
result += cal(depth+1,sum+i,n,dp);
}
dp[depth][sum] = result;
return result;
}
}
'알고리즘' 카테고리의 다른 글
백준 27737번 버섯 농장 (JAVA) (0) | 2023.06.13 |
---|---|
백준 9711번 피보나치 (JAVA) (0) | 2023.06.12 |
프로그래머스 리스트 자르기 (JAVA) (0) | 2023.06.10 |
프로그래머스 배열 만들기 4 (JAVA) (0) | 2023.06.09 |
백준 18223번 민준이와 마산 그리고 건우 (JAVA) (0) | 2023.06.08 |