백준 9095번( 자바 )
DP로 경우의 수 찾기
백준 9095번을 DP를 이용해 Java로 풀어봤다.
간단한 DP문제였고 문제를 보자마자 바로 풀긴 했지만 솔직히 더 큰 수들을 넣어줬을 때도 반드시 맞는다는 보장이 있는가 에 대해서는 조금 망설여졌다.
일단 제출하고 나서 다른 코드들도 살펴보며 생각해보니까 우리가 쓸 수 있는 수들은 1,2,3
으로 고정되어 있다. 따라서 n
을 만들고 싶을 때, 다음 세 가지 경우만 생각하면 된다.
n-3
+3
n-2
+2
n-1
+1
이렇게 세 가지 경우만이 우리가 사용할 수 있는 표현 방법의 전부이기 때문에 다음과 같은 간단한 점화식이 도출되는 것이다.
dp[n]
=dp[n-1]
+dp[n-2]
+dp[n-3]
아래는 내가 제출한 코드다.
import java.util.*;
import java.io.*;
public class boj9095 {
static int T,n,dp[] = new int[11];
static int DP(int n){
if(dp[n]!=0) return dp[n];
else{
for(int i=4; i<n+1; i++)
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
return dp[n];
}
}
public static void main(String args[]) throws IOException{
BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(bfr.readLine());
T = Integer.parseInt(stk.nextToken());
dp[1] = 1; dp[2] = 2; dp[3] = 4;
for(int i=0; i<T; i++){
stk = new StringTokenizer(bfr.readLine());
n = Integer.parseInt(stk.nextToken());
System.out.println(DP(n));
}
}
}
Author And Source
이 문제에 관하여(백준 9095번( 자바 )), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@topqr123q/백준-9095번-자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)