DP(Dynamic Programming = 동적 계획법)
하나의 큰 문제를 작은 문제로 나누어 결과를 저장하여 다시 큰 문제를 해결할 때 사용
재귀와 차이점
재귀를 사용하면 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 될 수 있다.
잘 정리된 블로그
if(a>b/2){
a=b-a;
}
이 코드를 적어주지 않으면 실패처리됨
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static int n,m,t;
public static boolean[] visited; //정점을 방문 했는지 true/false
public static StringBuilder sb=new StringBuilder();
public static int[][] arr;
static int ans;
public static void main(String[] args) {
t=scan.nextInt(); //테스트케이스
for(int i=0;i<t;i++) {
int a= scan.nextInt();
int b= scan.nextInt();
if(a==b) {
ans=1;
}
else {
//bCa 계산
if(a>b/2) {
a=b-a;
}
double answer=factorial(b,a)/factorial(a,a);
ans=(int)answer;
}
System.out.println(ans);
}
}
static double factorial(int a, int b) {
double ans = a;
for(int i=1;i<b;i++) { //b번
ans=ans*(a-i);
}
return ans;
}
}
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static int n,m,t;
public static boolean[] visited; //정점을 방문 했는지 true/false
public static StringBuilder sb=new StringBuilder();
public static int[] MAX,T,P;
static int ans,blue,white,cnt1,cnt2;
public static void main(String[] args) {
//입력
n=scan.nextInt(); //한변의 길이
MAX=new int[n+2];
T=new int[n+1];
P=new int[n+1];
for(int i=1;i<n+1;i++) {
T[i]=scan.nextInt();
P[i]=scan.nextInt();
}
for(int i=1;i<n+1;i++) {
int next=1;
next=i+T[i];
if(next<=n+1) {
MAX[next]=Math.max(findmax(i,MAX)+P[i], MAX[next]);
}
}
int max=0;
for(int i=1;i<n+2;i++) {
max=Math.max(MAX[i], max);
}
System.out.println(max);
}
static int findmax(int i, int[] max) {
int max1=0;
for(int j=1;j<=i;j++) {
max1=Math.max(max[j],max1);
}
return max1;
}
}