[ 4주차 ] 동적 계획법

📌 DP ( Dynamic Programming ) 

: 여러개의 하위 문제들을 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘, 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서 부터 차례로 구해나가 답을 알아내는 형태이다.

 

DP 문제중 최대값을 구하는 문제를 예를들면 

반복문으로 한걸을 한걸음 진행할때마다 그때마다 나올수있는 상황에서의 최대값을 구해준다.

arr[0]에서의 최대값

arr[1]에서의 최대값

arr[2]에서의 최대값

arr[3]에서의 최대값

마지막에 나오는 최대값이 답이다. 

 

🚩 연습문제1 - 백준 1003번 피보나치 함수

1003번: 피보나치 함수

 

숫자를 입력하면 1과 0이 몇번이나 출력되는지 알려주는 함수이다. 

피보나치 함수는 다음과 같은 형태다. 0 1 1 2 3 5 8 ..  규칙을 찾으면 된다.

0 에는 0이 1번, 1이 0번 출력된다

1 에는 0이 0번, 1이 1번 출력된다.

fibonachi(2) 는 fibocnachi(1) (2 - 1) , fibocnachi(0) (2 - 2)  으로 이루어져있기때문에

2 는 0에서의 0, 1번 + 1에서의 0, 0번 = 1번이 나오고 

      1에서의 1, 0번 + 1에서의 1, 1번 = 1번이 나온다.  따라서 0이 1번, 1이 1번 나온다.

쉽게말해서 뒤에 있는 숫자가 0이 몇번, 1이 몇번나온지를 그냥 더해주면 된다.

import java.util.Arrays;
import java.util.Scanner;


public class Main {
	public static void main(String[] args) {
		int input;
		int dp[][] = new int[41][2];
		Scanner sc = new Scanner(System.in);
		dp[0][0] = 1; dp[0][1] = 0; // 0은 0이 한번나오고 1은 안나온다.
		dp[1][0] = 0; dp[1][1] = 1; // 1은 0이 안나오고, 1은 한번나온다. (미리정의) 
		for (int i=2;i<=40;i++) {
			dp[i][0] = dp[i-1][0] + dp[i-2][0]; // 0에서 뒤에 두값(몇번나왔는지) 더해준다.
			dp[i][1] = dp[i-1][1] + dp[i-2][1]; // 1에서 .. 
		}
		input = sc.nextInt();
		for (int i=0;i<input;i++) {
			int x =sc.nextInt();
			System.out.println(dp[x][0]+" "+dp[x][1]);
		}
	}
}

 

🚩 연습문제2 -  백준 2775번 부녀회장이 될테야

2775번: 부녀회장이 될테야

k층 n호에 사는 사람들의 수는 (k층 n-1호) + (k-1층 n호)로 구해주면 된다. 

import java.util.Arrays;
import java.util.Scanner;


public class Main {
	public static void main(String[] args) {
		int [][]dp = new int[15][15];
		for (int i=1; i<=14;i++) {
			dp[0][i] = i; // 0층 초기화 
			dp[i][0] = 0; // 벽? 초기화
		}
		for (int i=1; i<=14;i++) {
			for (int j=1;j<=14;j++) {
				dp[i][j] = dp[i][j-1] + dp[i-1][j]; 
			}
		}
		Scanner sc = new Scanner(System.in);
		int k=0,n = 0;
		int T = sc.nextInt();
		for (int i=0; i<T;i++) {
			k = sc.nextInt(); n = sc.nextInt(); // k층, n호
			System.out.println(dp[k][n]);
		}

	}
} 

🚩 연습문제3 -  백준 9465번 스티커

9465번: 스티커

https://blog.naver.com/coke_mania/221537502952

[C] 백준 9465번 스티커

스티커 문제에 대한 자세한 설명은 위 블로그를 참고한다. 

import java.util.Arrays;
import java.util.Scanner;
import java.lang.Math;

public class test {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int i=0;i<T;i++) {
			int n = sc.nextInt();
			int sticker[][] = new int [2][n+1];
			int dp[][] = new int[2][n+1];
			for (int j=0;j<2;j++) {
				for (int k=0;k<n;k++) {
					sticker[j][k] = sc.nextInt();
				}
			} 
			dp[0][0] = sticker[0][0]; dp[1][0] = sticker[1][0];
			dp[0][1] = sticker[0][1] + sticker[1][0]; dp[1][1] = sticker[1][1] + sticker[0][0]; 
			
			for (int j=2;j<n;j++) {
				dp[0][j] = Math.max(dp[1][j-1],dp[1][j-2]) + sticker[0][j];
				dp[1][j] = Math.max(dp[0][j-1],dp[0][j-2]) + sticker[1][j];
			}
			System.out.println(Math.max(dp[0][n-1], dp[1][n-1]));
		}
	}
} 

 

🚩 실전문제 -  프로그래머스 등굣길

코딩테스트 연습 - 등굣길 | 프로그래머스

public static int solution(int m, int n, int[][] puddles) {
        
        int dp[][] = new int [n+1][m+1]; // n = y축 , m = x축 
        dp[1][1] = 1;      
        
        for (int i=0;i<puddles.length;i++) {
        	dp[puddles[i][1]][puddles[i][0]] = -1;       		
        }
              
        for (int i=1;i<=n;i++) {
        	for (int j=1;j<=m;j++) {
        		if (i==1 && j==1 ) continue;
        		if (dp[i][j] == -1) {
        			continue;
        		}
        		else if (dp[i-1][j] == -1 ) dp[i][j] = dp[i][j-1];
        		else if (dp[i][j-1] == -1 ) dp[i][j] = dp[i-1][j];
        		else dp[i][j] = ( dp[i-1][j] + dp[i][j-1]) %1000000007;
        	}
        	
        }

        return dp[n][m];
    }

🚩 실전문제 -  프로그래머스 도둑질

코딩테스트 연습 - 도둑질 | 프로그래머스

	public static int solution(int[] money) {
		int answer1 = 0,answer2=0;
		int len = money.length;
		int dp[] = new int[len];
		dp[0] = money[0];
		dp[1] = 0; dp[2] = money[0]+money[2];
		for (int i=3;i<len-1;i++) {
			dp[i] = Math.max(dp[i-2],dp[i-3]) + money[i];
		}
		answer1 = Math.max(dp[len-2],dp[len-3]);
		dp[0] = 0;
		dp[1] = money[1]; dp[2] = money[2];
		for (int i=3;i<len;i++) {
			dp[i] = Math.max(dp[i-2], dp[i-3])+ money[i];
		}
		answer2 = Math.max(dp[len-1],dp[len-2]);
		
		return Math.max(answer1, answer2);
    }

🚩 실전문제 -  프로그래머스 타일 장식물  

class Solution {
    public long solution(int N) {
		long answer;
        long[] dp = new long[N];
		dp[0] = 1; 
		dp[1] = 1; 
		for (int i=2;i<N;i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		answer = 2*dp[N-1] + 2*(dp[N-1]+dp[N-2]);
        return answer;
    }
}

🚩 실전문제 -  프로그래머스 정수 삼각형 

코딩테스트 연습 - 정수 삼각형 | 프로그래머스

 

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0, max = 0,len2;
        int len = triangle.length;
        int dp[][] = new int[len+1][len+1];
        dp[0][1] = triangle[0][0];
        for (int i=1; i<len; i++ ) {
        	len2 = triangle[i].length;
        	for (int j=1;j<=len2;j++) {
        		dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j-1];  
        	}
        }
        for (int i=1;i<=len;i++) {
        	if (dp[len-1][i] > max ) max = dp[len-1][i];
        }
        return max;
    }
}