[알고리즘] 백준알고리즘 DP

Posted by 신희준 on February 24, 2018


2018 - 02 - 24 (토)


백준알고리즘 DP


알고리즘 스터디를 구하고 어제 처음 모임을 가졌다. 첫 모임에서 주제로 다룬부분은 메모이제이션 이었다. 관련된 문제를 몇 문제 풀었는데, 기존에 내가 접근하던 방식과는 아주 달랐다.. 훨씬? 효율적인 방식을 알게 되었고 앞으로 체득화하기위해 계속 훈련해야 할 것 같다.

처음 으로 푼 문제는 역시 피보나치 수열이었다. 구글에 메모이제이션을 검색하면 대표적으로 나오는게 피보나치 였다..

문제이름 : 피보나치 함수 문제번호 : 1003 [https://www.acmicpc.net/problem/1003]

int fibonacci(int n) {
    if (n==0) {
        printf("0");
        return 0;
    } else if (n==1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}
  • 위 같은 경우에서 0이 출력되는 횟수와 1이 출력되는 횟수를 구하는 문제이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Pibonachi2 {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String args[])throws IOException{
		int N = Integer.parseInt(rd.readLine());

		int fiboZero[] = new int[41];
		int fiboOne[] = new int[41];

		fiboZero[0] = 1;
		fiboOne[0] = 0;
		fiboZero[1] = 0;
		fiboOne[1] = 1;

		for(int i =2; i < 41 ; i ++){
			fiboZero[i] = fiboZero[i-1] + fiboZero[i-2];
			fiboOne[i] = fiboOne[i-1] + fiboOne[i-2];
		}

		int temp[] = new int[N];

		for(int i= 0 ; i < N; i ++){
			temp[i] = Integer.parseInt(rd.readLine());
		}
		for(int i= 0 ; i <temp.length; i ++){

			System.out.println(fiboZero[temp[i]]+ " "+fiboOne[temp[i]]);
		}

	}
}

문제이름 : 2 x n 타일링 문제번호 : 11726 [https://www.acmicpc.net/problem/11726]

  • 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

  • 이 문제를 풀 때 점화식을 세웠다

  • dp[n] : 2*n 크기의 직사각형을 채우는 방법의 수를 10007로 나눈 나머지

  • 경우 1 ( 마지막에 2 x 1 의 직사각형이 있을 경우 ) dp[n] = dp[n-1] * 1

  • 경우 2 ( 마지막에 1 x 2 의 직사각형이 두개로 채워질 경우 ) dp[n] = dp[n-2] * 1

즉 이 두가지 경우를 더하고 10007 로 나누면 dp[n] 의 값을 알 수 있다.

  • dp[n] = (dp[n-1] + dp[n-2]) % 10007
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Tiling {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String args[])throws IOException{


		int N = Integer.parseInt(rd.readLine());
		int dp[] = new int[10001];

		dp[1] = 1;
		dp[2] = 2;

		for(int i =3; i < 10001; i ++){

			dp[i] = (dp[i-1]%10007+ dp[i-2]%10007)%10007;
		}
		System.out.println(dp[N]);


	}
}

문제이름 : 2xn 타일링 2 문제번호 : 11727 [https://www.acmicpc.net/problem/11727]

  • 2×n 직사각형을 2×1과 2×2, 1x2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. [첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)]

  • 이 문제를 풀 때 점화식을 세웠다

  • dp[n] : 2*n 크기의 직사각형을 채우는 방법의 수를 10007로 나눈 나머지

  • 경우 1 (2 * n-2 까지의 경우의 수에 남은 가로 2크기의 정사각형에 들어갈 수 있는 경우의 수는 3개 )

dp[n] = dp[n-2] * 3

  • 경우 2 (2 * n-3 까지의 경우의 수에 남은 가로 3크기의 정사각형에 들어갈 수 있는 경우의 수는 5개지만 경우 1과 겹치는 경우를 제외하면 2개가 남는다.)

  • dp[n] = ( dp[n-3] * 2 + dp[n-2] * 3 ) %10007

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Tiling2 {

	public static void main(String args[])throws IOException{

		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(rd.readLine());

		int dp[] = new int[10001];
		dp[1] = 1;
		dp[2] = 3;
		dp[3] = 5;
		for(int i =4; i <10001; i ++){

			dp[i] = (dp[i-3]*2%10007+dp[i-2]*3%10007)%10007;

		}

		System.out.println(dp[N]);
	}


}

문제이름 : 계단오르기 문제번호 : 2579 [https://www.acmicpc.net/problem/2579]

  • 규칙
    • 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
    • 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.
    • 마지막 도착 계단은 반드시 밟아야 한다.
  • 초기에 계단수를 입력 받고 계단수만큼 순서대로 각 계단의 점수를 입력해준다. 규칙대로 계단을 오를 수 있으며 최대값을 구한다.

  • 두가지 방법으로 나눌 수 있다.

  • 경우 1 (도착지점 이전 계단을 밟을 경우)

dp[n-3] + point[n-2]+ point[n-1] -> 도착지점 이전 계단을 밟은 경우

  • 경우 2 (도착지점 이전 계단을 밟지 않았을 경우)

dp[n-2] + point[n-1] -> 도착지점 이전 계단을 밟지 않은 경우

  • 즉 이 두가지 경우 중 최대값을 구하면 된다. point배열에 저장되어있는 값은 각 계단의 점수이다.

Math.max(dp[n-3] + point[n-2]+ point[n-1], dp[n-2] + point[n-1])

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;

public class UpStairs {
	public static void main(String args[])throws IOException{
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));


		int N = Integer.parseInt(rd.readLine());
		int dp[] = new int[N+1];
		//dp[] 의 정의는 조건을 만족하는 최대값점수 배열이다.
		int point[] = new int[N+1];

		for(int i =1; i <=N; i++){
			point[i] = Integer.parseInt(rd.readLine());
		}
		dp[0] = 0;
		dp[1] = point[1];
		dp[2] = point[1]+point[2];
		dp[3] = Math.max(point[1], point[2])+point[3];
		//두가지 방법으로 나눌 수 있다.
		//도착지점 이전 계단을 밟을 경우와 이전 계단을 밟지않았을 경우

		//점화식
		//dp[n-2] + point[n-1]  -> 도착지점 이전 계단을 밟지 않은 경우
		//dp[n-3] + point[n-2]+ point[n-1] -> 도착지점 이전 계단을 밟은 경우

		for(int i =4; i <=N; i++ ){
			dp[i] = Math.max(dp[i-2] + point[i], dp[i-3] + point[i]+point[i-1]);

		}
		System.out.println(dp[N]);
	}
}

문제이름 : 이동하기 문제번호 11048 [https://www.acmicpc.net/problem/11048]

문제 : 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최대값을 구하시오.

  • 세가지 방법으로 나눌 수 있다.

  • 경우 1 (도착지점에 오는 방법이 m+1 , m+1 인 경우)

d[n][m] = dp[n-1][m-1] + candy[n][m]

  • 경우 2 (도착지점에 오는 방법이 m+1 인 경우)

d[n][m] = dp[n][m-1] + candy[n][m]

  • 경우 3 (도착지점에 오는 방법이 n+1 인 경우)

d[n][m] = dp[n-1][m] + candy[n][m]

  • 즉 이 세가지 경우 중 최대값을 구하면 된다.

dp[n][m] += Math.max(dp[n][m-1], Math.max(dp[n-1][m], dp[n-1][m-1]));

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Move {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String args[])throws IOException{


	String temp = rd.readLine();

	int n = Integer.parseInt(temp.substring(0, temp.indexOf(" ")).trim());
	int m = Integer.parseInt(temp.substring(temp.indexOf(" ")+1).trim());
	int candy[][] = new int[n+1][m+1];


	for(int i =1;i <=n; i ++){
		String tmp[] = rd.readLine().split(" ");
		for(int j =1; j <=m; j++){

			candy[i][j] = Integer.parseInt(tmp[j-1].trim());

		}

	}
	for(int i =1; i <=n; i++){
		for(int j =1; j <= m ; j++){
			candy[i][j] += Math.max(candy[i][j-1], Math.max(candy[i-1][j], candy[i-1][j-1]));
		}
	}

	System.out.println(candy[n][m]);
	}

}