알고리즘 공부 #16 : DP

• DP(Dynamic Programming = 동적 계획법)
  하나의 큰 문제를 작은 문제로 나누어 결과를 저장하여 다시 큰 문제를 해결할 때 사용

• 재귀와 차이점
  재귀를 사용하면 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 될 수 있다.
  잘 정리된 블로그

백준 1010 : 다리 놓기

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;
    }
}

14501 : 퇴사

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;
    }
 }