TIL #8 다이나믹 프로그래밍 (2)

노력하는 배짱이·2020년 8월 13일
JavaTIL알고리즘
0

1. 다이나믹 프로그래밍 문제

1.1 문제 : 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구하는 문제이다. 예를 들어 A = [10,20,10,30,20,50] 이라 하면 가장 긴 증가하는 부분 수열은 [10,20,30,50] 이고 길이는 4이다.

이 문제의 점화식은 D[i] = A[1] ~ A[i] 까지 수열이 있을 때 A[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이이다.
즉, i=3 이고 A[1] = 10 , A[2] = 20 , A[3] = 10 라 했을 때 D[3] = 1 인 것이다.

i : 1 2 3
A[i] : 10 20 10
D[i] : 1 2 1
이러한 형태로 나오게 되는 것이다.
정리하자면 처음에 i=1일 때 하나 뿐이니까 D[1] = 1이고 앞에 나오는 수가 없으니까 넘어간다. i=2일 때 이 수가 하나라 생각하면 D[2]=1 이다. 이 수의 앞에 나온 것(A[1]에 해당하겠죠?)이 A[2] 보다 작은지 판단했을 때 작으면 D[1]에다가 +1를 한 값을 D[2]에 넣어준다. 이제 i=3일 때를 보자 마찬가지로 하나뿐이라고 생각했을 때 1를 넣어준다. A[2]와 비교를 하는데 A[2] > A[3] 이기 때문에 넘어가고, A[1]과 비교를 하는데 또 같은 수이기 때문에 넘어가서 결국 D[3] = 1 이 된다.

결국에는 A[i] 앞에 나오는 수를 봐야하는데 어떤 수가 나오는지는 알 수 없기 때문에 A[j]로 표현할 수 있다. 그러면 A[j] 는 A[i] 보다 작게 되는 것이고 j < i 라는 조건도 붙게 된다.

따라서 D[i] = max(D[j]) + 1 (j<i, A[j] < A[i]) 라고 정의할 수 있다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] a = new int[n];
	for (int i = 0; i < n; i++) {
		a[i] = sc.nextInt();
	}
	int[] d = new int[n];
	for (int i = 0; i < n; i++) {
		d[i] = 1;
		for (int j = 0; j < i; j++) {
			if (a[j] < a[i] && d[i] < d[j] + 1) {
				d[i] = d[j] + 1;
			}
		}
	}
	int r = d[0];
	for (int i = 0; i < n; i++) {
		if (r < d[i]) {
			r = d[i];
		}
	}
	System.out.println(r);
}

1.2 문제 : 가장 긴 증가하는 부분 수열 4

1.1 문제와 같지만 출력할 때 길이 뿐만 아니라 가장 긴 증가하는 부분 수열도 같이 출력하는 문제이다.

접근 방법은 역추적 과정을 해야하는데, D[i]를 구할 때마다 영향을 받은 i번째 수열의 인덱스 값을 저장하는 것이다. 만약에 D[4]의 값이 3이되는 것이 D[2]로 인해 생기는 것이라면 인덱스를 저장하는 V[4]의 값은 2인 것이다.

역추적 과정은 주로 재귀함수를 이용하여 구현한다.

public static int[] a;
public static int[] d;
public static int[] v;
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	a = new int[n];
	for (int i = 0; i < n; i++) {
		a[i] = sc.nextInt();
	}
	d = new int[n];
	v = new int[n];
	for (int i = 0; i < n; i++) {
		d[i] = 1;
		v[i] = -1;
		for (int j = 0; j < i; j++) {
			if (a[j] < a[i] && d[i] < d[j] + 1) {
				d[i] = d[j] + 1;
				v[i] = j;
			}
		}
	}
	int r = d[0];
	int p = 0;
	for (int i = 0; i < n; i++) {
		if (r < d[i]) {
			r = d[i];
			p = i;
		}
	}
	System.out.println(r);
	go(p);
}
public static void go(int p) {
	if(p == -1) {
		return;
	}
	go(v[p]);
	System.out.print(a[p] + " ");
}

1.3 문제 : 연속합

n개의 정수로 이루어진 임의의 수열이 주어지고 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제이다.

흔히 생각할 수 있는 것이 음수인 것들을 제외할 수 있는 점인데 이는 3,-1,3형태이면 합이 5가 나오는 경우가 있어서 이 조건은 할 수 없다.

점화식을 생각해보자.
D[i] = i번째 수로 끝나면서 가장 큰 연속합이라고 정의할 수 있다.

그러면 i번째 수에 가능한 경우의 수를 생각하자.
첫 번째는 i번째 수는 i-1번째 수의 연속합에 포함되는 경우이고, 두 번째는 i번째 수가 새로운 연속합을 시작하는 경우이다.

첫 번째 경우 i-1 번째에서 나온 D[i-1]에다가 i번째의 수를 더하면 된다. 즉, D[i-1] + A[i]
두 번째 경우 앞서 구한 D[i]값들을 생각하지 말고 자기 자신 A[i] 값을 넣어주면 된다.
따라서 D[i] = max(D[i-1] + A[i] , A[i])라고 정의할 수 있다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] a = new int[n];
	for (int i = 0; i < n; i++) {
		a[i] = sc.nextInt();
	}
	int[] d = new int[n];
	for (int i = 0; i < n; i++) {
		d[i] = a[i]; // 새로운 연속합을 시작하는 경우
		if (i == 0) {
			continue;
		}
		if (d[i] < d[i - 1] + a[i]) { // i-1번째의 연속합에 포함되는 경우
			d[i] = d[i - 1] + a[i];
		}
	}
	int r = d[0];
	for (int i = 0; i < n; i++) {
		if (r < d[i]) {
			r = d[i];
		}
	}
	System.out.println(r);
}

1.4 문제 : 제곱수의 합

주어진 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제이다.

앞서 풀었던 1,2,3 더하기 문제와 유사하다.
마지막에 오는 수를 살펴보자. 121^2, 222^2, 323^2 ... 이렇게 올 수 있는데 너무 많으니까 변수 j로 두자.
D[i] = i를 제곱수의 합으로 나타냈을 때 필요한 항의 최소 개수 라고 정의를 하자.
그러면 마지막 항이 j2j^2이라면 앞에는 합이 i−j2i-j^2 이고 항의 최소 개수는 D[i−j2]D[i-j^2] 이라고 할 수 있다. j2j^2 부분은 항이 1개니까 D[i−j2]+1D[i-j^2] + 1 를 할 수있다.
다시 정리하면 j의 범위는 1≤j2≤i1 \leq j^2 \leq i 이기 때문에 D[N] = min(D[i−j2])+1min(D[i-j^2]) +1 이라고 정의할 수 있다. 

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] d = new int[n + 1];
	for (int i = 1; i <= n; i++) {
		d[i] = i;
		for (int j = 1; j * j <= i; j++) {
			if (d[i] > d[i - j * j] + 1) {
				d[i] = d[i - j * j] + 1;
			}
		}
	}
	System.out.println(d[n]);
}

1.5 문제 : 합분해

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제이다.
O + O + ... + O = N (O의 개수가 K개)이라고 생각하면 마지막 O에 들어갈 수 있는 수는 0부터 N까지이다. 마지막 O 를 변수 L로 생각해보자.

그러면 L 이전까지의 합은 N-L 이고 ( (N-L) + L = N) N-L부분의 개수는 K-1개이다. L의 범위는 0≤L≤N0 \leq L \leq N이니까 점화식을 정의하면 D[K][N] = 0부터 N까지 K개를 더해서 그 합이 N이 되는 경우의 수 이라 했을 때 D[K][N] = ΣD[K−1][N−L]\Sigma D[K-1][N-L] 이라고 할 수 있다.

public static long mod = 1000000000L;
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int k = sc.nextInt();
	long[][] d = new long[k + 1][n + 1];
	d[0][0] = 1;
	for (int i = 1; i <= k; i++) { // k 값
		for (int j = 0; j <= n; j++) { // n 값
			for (int l = 0; l <= j; l++) { // 마지막 수 l
				d[i][j] += d[i - 1][j - l];
				d[i][j] %= mod;
			}
		}
	}
	System.out.println(d[k][n]);
}

1.6 문제 : 1,2,3 더하기 3

이전에 풀었던 1,2,3 더하기 문제와 유사하게 풀면 된다.
d[n] = 1, 2, 3의 합으로 나타내는 방법의 수 라고 정의하자.
그러면 마지막에 오는 수가 1, 2, 3 이 경우를 고려하면 d[n] = d[n-1] + d[n-2] + d[n-3] 이 된다.

이 점화식은 이전 게시글에 있는 1, 2, 3 더하기 문제에 적혀있다.

public static final long mod = 1000000009L;
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int t = sc.nextInt();
	long[] d = new long[1000001];
	d[0] = 1;
	for(int i=1; i<=1000000; i++) {
		for(int j=1; j<=3; j++){
			if(i-j >= 0) {
				d[i] += d[i-j];
			}
		}
		d[i] %= mod;
	}
	while(t-- > 0) {
		int n = sc.nextInt();
		System.out.println(d[n]);
	}
}

1.7 문제 : RGB 거리

해당 문제는 1, 2, 3 더하기 5 문제와 유사하다.
문제 조건으로 이웃하는 집은 같은 색으로 칠할 수 없다 라는 것이 주어졌는데, 1, 2, 3 더하기 5 문제처럼 연속하는 수가 올 수 없다는 식으로 생각할 수 있다.

즉, 마지막에 빨강이 오면 앞에는 초록 또는 파랑이 올 수 있고 초록이 오면 앞에는 빨강 또는 파랑이 올 수 있다.
이를 토대로 점화식을 정의하자면, d[i][j] = i번 집을 j색으로 칠했을 때 1~i번 집을 칠하는 비용의 최솟값 이라고 정의할 수 있다.

또한 비용에 대해서는 A[i][j] = i번 집을 색 j로 칠하는 비용의 최솟값 으로 정의 할 수 있다.

d[i][0] = min(d[i-1][1], d[i-1][2]) + A[i][0] 이라는 하나의 식으로 나아갈 수 있으며, d[i][j] = min(d[i][0], d[i][1], d[i][2])으로 결론을 지을 수 있다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[][] a = new int[n+1][3];
	int[][] d = new int[n+1][3];
	for(int i=1; i<=n; i++) {
		for(int j=0;j<3;j++) {
			a[i][j] = sc.nextInt();
		}
	}
	for(int i=1; i<=n; i++) {
		d[i][0] = Math.min(d[i-1][1], d[i-1][2]) + a[i][0];
		d[i][1] = Math.min(d[i-1][0], d[i-1][2]) + a[i][1];
		d[i][2] = Math.min(d[i-1][0], d[i-1][1]) + a[i][2];
	}
	System.out.println(Math.min(Math.min(d[n][0], d[n][1]),d[n][2]));
}

1.8 문제 : 동물원

동물원 문제의 조건으로 가로, 세로로 붙어 있게 배치하면 안된다 라는 것이 주어졌다.
n=1일 때 가로줄이 하나일 때를 생각해보면 사자를 배치하지 않은 경우, 사자를 왼쪽에 배치하는 경우, 사자를 오른쪽에 배치하는 경우 이 3가지로 나뉘어 질 수 있다.

이를 기반으로 점화식을 세울 수 있다.
d[n][0] = n번 줄에 사자를 배치하지 않는 경우
d[n][1] = n번 줄에 사자를 왼쪽에 배치하는 경우
d[n][2] = n번 줄에 사자를 오른쪽에 배치하는 경우

d[n][0] = d[n-1][0] + d[n-1][1] + d[n-1][2]
d[n][1] = d[n-1][0] + d[n-1][2]
d[n][2] = d[n-1][0] + d[n-1[1]

d[n][1]를 보면, n번째 줄에 왼쪽에 배치하는 경우인데 n-1번째 줄에는 배치를 하지 않거나 오른쪽에 배치해야하기 때문에 위와 같은 식이 나온 것이다.

따라서 모든 경우의 수는 d[n][0] + d[n][1] + d[n][2]라고 할 수 있다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[][] d = new int[n + 1][3];
	d[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		d[i][0] = d[i - 1][0] + d[i - 1][1] + d[i - 1][2];
		d[i][1] = d[i - 1][0] + d[i - 1][2];
		d[i][2] = d[i - 1][0] + d[i - 1][1];
		for (int j = 0; j < 3; j++) {
			d[i][j] %= 9901;
		}
	}
	System.out.println((d[n][0] + d[n][1] + d[n][2]) % 9901);
}

1.9 문제 : 오르막 수

오르막 수 문제는 계단 수 문제와 유사하다. 수의 길이 n이 주어질 때 오르막 수의 개수를 구하는 문제이다.
예를들면 123345라는 수가 오르막 수 이다.

마지막에 오는 수가 L이라 했을 때 계단 수 문제에서는 앞에 올 수 있는 수는 L-1, L+1이 지만 이 문제에서는 앞에 올 수 있는 수는 1부터 L까지이다. 이를 K로 정의하면 0≤K≤L0\leq K \leq L이라는 범위를 알 수 있다.

d[i][j] = 길이가 i이면서 마지막 수가 j인 오르막 수의 개수 라고 정의하자. 그러면 길이가 1일때 즉 d[1][j]일때는 0부터 9까지 다 가능하니까 d[i][j] = 1 이라고 할 수 있다.
d[i][j] = Σd[i−1][k]\Sigma{d[i-1][k]} (0≤k≤j0 \leq k \leq j)라고 점화식을 세울 수 있다. 

public static long mod = 10007;
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	long[][] d = new long[n + 1][10];
	for (int i = 0; i <= 9; i++) {
		d[1][i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = 0; k <= j; k++) {
				d[i][j] += d[i - 1][k];
				d[i][j] %= mod;
			}
		}
	}
	long result = 0;
	for (int i = 0; i < 10; i++) {
		result += d[n][i];
	}
	result %= mod;
	System.out.println(result);
}

1.10 문제 : 스티커

2xn 모양으로 배치된 스티커에서 점수의 합의 최대값을 구하는 문제이다.
이 문제는 앞서 풀었던 동물원 문제와 비슷하다.

d[i][j] = 2 x i 에서 얻을 수 있는 최대 점수이며, i번 열에서 뜯는 스티커는 j 라는 정의를 할 수 있다.
j = 0 이면 뜯지 않은 것이고, 1이면 위쪽, 2이면 아래쪽을 뜯는 것을 의미한다.
j = 0 이면 i-1 열에는 어떤 스티커를 뜯는지 상관 없기 때문에 max(d[i-1][0], d[i-1][1], d[i-1][2])를 구하면 되고, j = 1이면 i-1열 에는 위쪽 스티커를 제외한 나머지를 구하면 된다. 즉 max(d[i-1][0], d[i-1][2]) 에다가 A[i][0] 을 더해주면 된다.
A[i][0] 은 i 번째열의 첫번째 줄에 해당하는 점수이다.
j = 2 일 때 동일하게 구하면 된다.

public static void main(String[] args) throws IOException {
	Scanner sc = new Scanner(System.in);
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int t = Integer.valueOf(br.readLine());
	while (t-- > 0) {
		int n = Integer.valueOf(br.readLine());
		long[][] a = new long[n + 1][2];
		String[] line = br.readLine().split(" ");
		for (int i = 1; i <= n; i++) {
			a[i][0] = Long.valueOf(line[i - 1]);
		}
		String[] line2 = br.readLine().split(" ");
		for (int i = 1; i <= n; i++) {
			a[i][1] = Long.valueOf(line2[i - 1]);
		}
		long[][] d = new long[n + 1][3];
		for (int i = 1; i <= n; i++) {
			d[i][0] = Math.max(d[i - 1][0], Math.max(d[i - 1][1], d[i - 1][2]));
			d[i][1] = Math.max(d[i - 1][0], d[i - 1][2]) + a[i][0];
			d[i][2] = Math.max(d[i - 1][0], d[i - 1][1]) + a[i][1];
		}
		long ans = 0;
		ans = Math.max(d[n][0], Math.max(d[n][1], d[n][2]));
		System.out.println(ans);
	}
}

1.11 문제 : 포도주 시식

이 문제의 조건으로 연속으로 놓여 있는 3잔을 모두 마실수 없다. 라는 것이 주어졌다. 이를 활용하여 점화식을 세워야 한다.
d[i] = a[1] ~ a[i] 가지 포도주를 마셧을 때 마실 수 있는 포도주의 최대 양이라고 정의할 수 있다.
경우의 수를 생각하면 0번 연속해서 마신 포도주일 때 a[i]를 마시지 않은 것이고, 1번 연속해서 마신 포도주이면 a[i-1]를 마시지 않은 것이다. 2번 연속해서 마신 포도주이면 a[i-1]를 마시고 a[i-2]는 마시지 않는 것이다.

정리하면 0번 연속은 d[i-1] 이고 1번 연속은 d[i-2] + a[i] 그리고 2번 연속은 d[i-3] + a[i-1] + a[i] 이다.

따라서 d[i] = max(d[i-1], d[i-2] + a[i], d[i-3] + a[i-1] + a[i] ) 이다.
이때 i-2, i-3 부분을 예외처리 해야하기 때문에 d[1] = a[1], d[2] = a[1] + a[2]로 미리 처리해야 한다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] a = new int[n + 1];
	for (int i = 1; i <= n; i++) {
		a[i] = sc.nextInt();
	}
	int[] d = new int[n + 1];
	d[1] = a[1];
	if (n >= 2) {
		d[2] = a[1] + a[2];
	}
	for (int i = 3; i <= n; i++) {
		d[i] = d[i - 1];
		d[i] = Math.max(d[i], d[i - 2] + a[i]);
		d[i] = Math.max(d[i], d[i - 3] + a[i - 1] + a[i]);
	}
	int ans = d[1];
	for (int i = 2; i <= n; i++) {
		ans = Math.max(ans, d[i]);
	}
	System.out.println(ans);
}

1.12 문제 : 정수 삼각형

정수 삼각형 문제에서 아래로 내려가려면 대각선 왼족 또는 대각선 오른쪽을 선택할 수 있다고 한다. 반대로 임의의 줄에서 하나를 기준으로 이전으로 가려면 왼쪽 위나 혹은 오른쪽 위를 선택할 수 있다.

d[i][j] = i행 j열이 선택되었을때 최대합이라 정의할 수 있다. (i,j)가 선택되기 이전에는 (i-1, j) 또는 (i-1, j-1) 중 하나가 올 수 있다.
따라서 d[i][j] = max(d[i-1][j], d[i-1][j-1])이다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[][] a = new int[n][n];
	int[][] d = new int[n][n];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			a[i][j] = sc.nextInt();
		}
	}
	d[0][0] = a[0][0];
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			d[i][j] = d[i - 1][j] + a[i][j];
			if (j - 1 >= 0 && d[i][j] < d[i - 1][j - 1] + a[i][j]) {
				d[i][j] = d[i - 1][j - 1] + a[i][j];
			}
		}
	}
	int ans = d[n - 1][0];
	for (int i = 0; i < n; i++) {
		if (ans < d[n - 1][i]) {
			ans = d[n - 1][i];
		}
	}
	System.out.println(ans);
}

1.13 문제 : 가장 큰 증가하는 부분 수열

1.1 문제와 유사한 문제이다. '긴' 에서 '큰'으로 바뀐 문제이다. 1.1 문제를 토대로 점화식을 이 문제에 맞게 세우면 d[i] = i번째에서 끝나는 증가부분 수열의 합의 최댓값 이라 할 수 있다.

마지막 수가 a[i]라 했을 때 앞에는 a[j]가 올 수 있고, a[j] 까지의 최대 합은 d[j]라 할 수 있다. j 는 i보다 작으며 a[j] 역시 a[i]보다 작아야 한다.

따라서 d[i] = max(d[j] + a[i]) 라고 할 수 있다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] a = new int[n];
	for(int i =0; i<n;i++) {
		a[i] = sc.nextInt();
	}
	int[] d = new int [n];
	for(int i=0; i<n; i++) {
		d[i] = a[i];
		for(int j =0; j<i; j++) {
			if(a[j] < a[i] && d[i] < d[j] + a[i]) {
				d[i] = d[j] + a[i];
			}
		}
	}
	int ans = d[0];
	for(int i =0; i<n; i++) {
		if(ans < d[i]) {
			ans = d[i];
		}
	}
	System.out.println(ans);
}

1.14 문제 : 가장 긴 감소하는 부분 수열

이 문제는 두가지의 방법이 있다.
첫번째 방법은 주어진 수열 a를 순서를 뒤집어서 가장 긴 증가하는 부분 수열을 구하는 방법이다.
또다른 방법의 점화식은 d[i] = a[i]에서 시작하는 가장 긴 감소하는 부분 수열의 길이 라고 정의할 수 있다.
a[i]가 시작하는 수이면 이 다음에는 a[j]가 올 수 있는데 이때 i<j 이고 a[i] > a[j] 이어야 한다.
따라서 d[i] = max(d[j]) + 1 이다.

이는 LIS(가장 긴 증가하는 부분 수열)방법을 그대로 적용하기에는 문제가 있다. 이유는 a[i]번째부터 시작하면 뒤에 있는 걸 다 구해둬야 하는데 처음부터 시작하면 힘들기 때문이다. 그래서 맨 마지막 n번째 부터 해서 n-1, n-2 이렇게 진행해야 한다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] a = new int[n+1];
	int[] d = new int[n+1];
	for(int i=1;i<=n;i++) {
		a[i] = sc.nextInt();
	}
	for(int i=n; i>=1; i--) {
		d[i]= 1;
		for(int j=i+1; j<=n; j++) {
			if(a[i] > a[j] && d[i] < d[j] + 1) {
				d[i] = d[j] + 1;
			}
		}
	}
	int ans = d[1];
	for(int i=2; i<=n; i++) {
		if(ans < d[i]) {
			ans = d[i];
		}
	}
	System.out.println(ans);
}

이와 비슷하게 또다른 방식은 d[i] = a[i]에서 끝나는 가장 긴 감소하는 부분 수열의 길이 라고 두는 것이다.
a[i] 이전에는 a[j]가 올 수 있고, j<i 이고 a[j] > a[i] 이어야 한다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] a = new int[n + 1];
	int[] d = new int[n + 1];
	for (int i = 1; i <= n; i++) {
		a[i] = sc.nextInt();
	}
	for (int i = 1; i <= n; i++) {
		d[i] = 1;
		for (int j = 1; j <= i; j++) {
			if (a[j] > a[i] && d[i] < d[j] + 1) {
				d[i] = d[j] + 1;
			}
		}
	}
	int ans = d[1];
	for (int i = 2; i <= n; i++) {
		if (ans < d[i]) {
			ans = d[i];
		}
	}
	System.out.println(ans);
}

1.15 문제 : 가장 긴 바이토닉 부분 수열

해당 문제는 수열 a가 주어졌을 때, 그 수열의 바이토닉 부분 수열 중에서 가장 긴 것을 구하는 문제이다.
이 문제는 점화식을 두개 사용해야 한다. 하나는 가장 긴 부분수열 점화식이고 다른 하나는 가장 긴 감소하는 부분수열 점화식이다.

d[i] = i에서 끝나는 가장 긴 증가하는 부분 수열
d2[i] = i에서 시작하는 가장 긴 감소하는 부분 수열
이라 하면 d[i] + d2[i] -1 이 가장 큰 값을 찾으면 된다.
이때 -1를 하는 이유는 i번째가 중복이 되기 때문이다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] a = new int[n];
	for (int i = 0; i < n; i++) {
		a[i] = sc.nextInt();
	}
	int[] d = new int[n];
	for (int i = 0; i < n; i++) {
		d[i] = 1;
		for (int j = 0; j < i; j++) {
			if (a[j] < a[i] && d[i] < d[j] + 1) {
				d[i] = d[j] + 1;
			}
		}
	}
	int[] d2 = new int[n];
	for (int i = n - 1; i >= 0; i--) {
		d2[i] = 1;
		for (int j = i + 1; j < n; j++) {
			if (a[i] > a[j] && d2[j] + 1 > d2[i]) {
				d2[i] = d2[j] + 1;
			}
		}
	}
	int ans = d[0] + d2[0] - 1;
	for (int i = 0; i < n; i++) {
		if (ans < d[i] + d2[i] - 1) {
			ans = d[i] + d2[i] - 1;
		}
	}
	System.out.println(ans);
}

1.16 문제 : 연속합 2

이 문제는 연속합 문제에 한가지 조건이 추가된 문제이다. 조건은 어떤 수를 하나 제거하거나 제거하지 않아도 된다. 이다.

이 문제를 하나씩 제거하고 연속합을 구하는 방식으로 하면 시간이 오래걸리기 때문에 다른 방식으로 풀어야하는데 앞서 푼 바이토닉 문제처럼 접근하면 된다.

d[i]를 i번째에서 끝나는 연속합이라 하고 d2[i]를 i번째에서 시작하는 연속합이라 두는 것이다.
즉 k번째를 제거하면 k-1번째 k+1번째 를 고려하여 k-1번재에서 끝나는 연속합과 k+1에서 시작하는 연속합을 구하면 되는것이다. 따라서 d[k-1] + d2[k+1]를 구하면 된다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] a = new int[n];
	for (int i = 0; i < n; i++) {
		a[i] = sc.nextInt();
	}
	int[] d = new int[n];
	int[] dr = new int[n];
	for (int i = 0; i < n; i++) {
		d[i] = a[i];
		if (i > 0 && d[i] < d[i - 1] + a[i]) {
			d[i] = d[i - 1] + a[i];
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		dr[i] = a[i];
		if (i < n - 1 && dr[i] < dr[i + 1] + a[i]) {
			dr[i] = dr[i + 1] + a[i];
		}
	}
	int ans = d[0];
	for (int i = 1; i < n; i++) {
		if (ans < d[i]) {
			ans = d[i];
		}
	}
	for (int i = 1; i < n - 1; i++) {
		if (ans < d[i - 1] + dr[i + 1]) {
			ans = d[i - 1] + dr[i + 1];
		}
	}
	System.out.println(ans);
}

1.17 문제 : 타일 채우기

3 x N을 1 x 2 , 2 x 1 로 채우는 방법의 수를 구하는 문제이다. d[i] = 3 x i를 채우는 방법의 수라고 정의할 수 있다.

N번째에 올 수 있는 가능한 경우의 수를 보면
1. 위에 2x1 두개 아래에 1x2 하나
2. 위에 1x2 하나 아래에 2x1 두개
3. 1x2 세개

이렇게 경우가 나뉘어진다. 이 N번째 타일의 길이는 2가 나오기 때문에 이전의 타일의 길이는 n-2가 된다. 따라서 점화식은 d[n] = d[n-2] * 3 이 된다.

하지만 이것으로 끝난 것이 아니라 n번째 타일이 길이가 4인 경우 6인 경우 ... 더 있기 때문에 d[n] = 3d[n-2] + 2d[n-4] + 2*d[n-6] .... 으로 식이 정의된다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	long[] d = new long[n + 1];
	d[0] = 1;
	for (int i = 2; i <= n; i += 2) {
		d[i] = d[i - 2] * 3;
		for (int j = i - 4; j >= 0; j -= 2) {
			d[i] += d[j] * 2;
		}
	}
	System.out.println(d[n]);
}

1.18 문제 : RGB 거리 2

이전 RGB 거리 문제와 같은데 1번째 집과 마지막 집이 이웃이라는 점이 다르다.
RGB 거리 문제처럼 점화식을 세워 구하면 되는데 어떻게 1번집과 마지막 집의 색이 다르게 할 수 있을까?

바로 1번 집의 색을 고정시키고 답을 구하면 된다. 1번 집의 색이 빨강이라면 마지막 집은 초록, 파랑 2가지가 올 수 있고 마찬가지로 초록 또는 파랑이 올 때도 동일하다 이렇게 총 6가지가 가능하다.

점화식은 D[i][j] = i번 집을 색 j로 칠했을 때, 1부터 i번 집을 칠하는 비용의 최소값이다. 그러면 1번 집의 색을 빨강이라 했을 때 마지막 집 (N번 집)의 값은 D[N][1], D[N][2] 이 두개가 되고 여기에 최소값을 구하면 된다.

따라서 1번 집의 색을 미리 정하고 다이나믹을 총 3번을 수행해야만 답을 구할 수 있다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[][] a = new int[n + 1][3];
	int[][] d = new int[n + 1][3];
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			a[i][j] = sc.nextInt();
		}
	}
	int ans = 1000 * 1000 + 1; 
	for (int k = 0; k <= 2; k++) { // 첫번째 집의 색 고정
		for (int j = 0; j <= 2; j++) {
			if (j == k) {
				d[1][j] = a[1][j];
			} else {
				d[1][j] = 1000 * 1000 + 1; // 임의의 큰 수
			}
		}
		for (int i = 2; i <= n; i++) {
			d[i][0] = Math.min(d[i - 1][1], d[i - 1][2]) + a[i][0];
			d[i][1] = Math.min(d[i - 1][0], d[i - 1][2]) + a[i][1];
			d[i][2] = Math.min(d[i - 1][0], d[i - 1][1]) + a[i][2];
		}
		for (int j = 0; j <= 2; j++) { // N번 집의 색
			if (j == k) {
				continue;
			}
			ans = Math.min(ans, d[n][j]);
		}
	}
	System.out.println(ans);
}

참고

백준 알고리즘 기초 강의를 듣고 공부하기 위해 정리한 것입니다.

profile
노력하는 배짱이
이전 포스트

TIL #7 다이나믹 프로그래밍 (1)

다음 포스트

TIL #9 브루트 포스 (1)

0개의 댓글