[코딩테스트] 다이나믹 프로그래밍(포도주시식~)
reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.
포도주 시식(2156번)
https://www.acmicpc.net/problem/2156
문제
- 포도주가 일렬로 높여져 있고, 다음과 같은 2가지 규칙을 지키면서 포도주를 최대한 많이 마시려고 한다.
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
풀이
2차원 풀이
- i번 포도주의 양 A[i]
- 몇 잔의 포도주를 현재까지 마셨는가가 중요
- D[i][j] = i번째 포도주까지 있고 그 때 A[i]는 j번 연속해서 마신 포도주
- D[i][0] = 0번 연속해서 마신 포도주, A[i]를 마시지 않음
앞엔 몇갤 마시던지 상관 없음 = max(D[i-1][0], D[i-1][1], D[i-1][2]) - D[i][1] = 1번 연속해서 마신 포도주, A[i-1]를 마시지 않음
= D[i-1][0]+A[i] - D[i][2] = 2번 연속해서 마신 포도주, A[i-1]를 마시고, A[i-2]를 마시지 않음
= D[i-1][1]+A[i]
1차원 풀이
- 이친수 0 아니면 1이니까 1차원으로 풀었었다. 이 문제도 포도주를 마시지 않았으면 0, 마셨으면 1로 볼 수 있음.
- D[i] = A[1], …, A[i]까지 포도주를 마셨을 때, 마실 수 있는 포도주의 최대 양
- 0번 연속해서 마신 포도주 -> A[i]를 마시지 않음 = D[i-1]
- 1번 연속해서 마신 포도주 -> A[i-1]를 마시지 않음 = D[i-2] + A[i]
- 2번 연속해서 마신 포도주 -> A[i-1]를 마시고 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])
- 초기값 D[1] = A[1], D[2] = A[1]+A[2] 로 미리 처리 해주고 i=3부터 풀기
import java.util.*;
public class Main {
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] = Math.max(d[i-1], Math.max(d[i-2]+a[i],d[i-3]+a[i-1]+a[i]));
}
int ans = d[1];
for(int i=2; i<=n; i++) {
if(ans<=d[i])
ans=d[i];
}
System.out.println(ans);
}
}
-> 문제마다 다르겠지만 1차원으로도 풀 수 있는 방법을 생각할 줄 알아야 할거같다. 훨씬 간단ㅠ 그리고 d[2] = a[1]+a[2] 같은 경우엔 n>=2일때 라고 조건 제대로 달아주기…
정수삼각형(1932번)
https://www.acmicpc.net/problem/1932
문제
- i번행 i개의 삼각형, 대각선 왼쪽 아래/오른쪽으로만 이동 가능, 만난 수의 합의 최대값
풀이
- 아래층으로 내려올 땐 대각선 왼쪽, 또는 대각선 오른쪽에 있는 것만 선택 가능
- 여기에 왔다. 근데 그 전엔 어디에 있었을까? 로 생각해서 풀기
- 반대로 생각하면 어떤 수가 선택되기 전 수는 대각선 왼쪽 위, 오른쪽 위에 있음
- D[i][j] = i번행의 j번째 수, (i,j)에 도착했을 때 합의 최대값
- (i+1,j) <- (i,j) -> (i+1,j+1) 를 반대로 생각하면
- (i-1,j-1) -> (i,j) <- (i-1,j)
- D[i][j] = max(D[i-1][j-1],D[i-1][j]) + A[i][j]
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] a = new int[n+1][n+1];
for(int i=1; i<=n; i++) {
for(int j=1; j<=i; j++) {
a[i][j] = sc.nextInt();
}
}
int[][] d = new int[n+1][n+1];
d[1][1] = a[1][1]; // 초기화
for(int i=2; i<=n; i++) {
for(int j=1; j<=i; j++) {
d[i][j] = Math.max(d[i-1][j-1], d[i-1][j])+a[i][j];
}
}
int ans = 0;
for(int j=1; j<=n; j++) {
if(ans<=d[n][j])
ans = d[n][j];
}
System.out.println(ans);
}
}
가장 큰 증가하는 부분 수열(11055번)
https://www.acmicpc.net/problem/11055
문제
- 수열 i가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 문제
풀이
- 가장 긴 : D[i] = i번까지 있을때 가장 긴 길이, A[j] A[i] 일때 j < i, A[j] < A[i]
- A[i]제외한 A[j]까지의 길이는 D[j], A[i]를 더하면 길이 +1
- max(D[j]) + 1
- 초기값 D[i] = 1
- 가장 큰 : D[i] = i번까지 있을 때 최대 합
- 부분수열이기에 j < i, A[j] < A[i] 조건 동일
- max(D[j]) + A[i]
- 초기값 D[i] = A[i] : 앞에 수가 없어도 하나만 있어도 부분 수열이 되니까.
import java.util.*;
public class Main {
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);
}
}
가장 긴 감소하는 부분 수열(11722번)
https://www.acmicpc.net/problem/11722
문제
- 수열 A가 주어졌을 때, 그 수열의 감소하는 부분 수열 중 가장 긴 것을 구하는 문제
풀이
- 세 가지 방법 이 있음
- 입력으로 주어진 수열 A를 뒤집어서 가장 긴 증가하는 부분 수열을 구하는 방법
- 가장 긴 증가하는 부분 수열과 비슷하게 구하는 방법(뒤에서부터 구현해야 함)
- 2번 풀이
- D[i] = A[i]에서 끝나는 가장 긴 감소하는 부분수열의 길이
- j < i, A[j] > A[i]
- A[j] / A[i] 라고 하면 A[j]까지의 길이는 D[j], A[i]를 더하면 max(D[j]+1)
- A[i]로 시작하는 방법
import java.util.*;
public class Main {
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];
for(int i=n; i>0; i--) {
d[i] = 1;
for(int j=i+1; j<=n; j++) { //여기 for문 조건 작성 어려웠다..ㅠ
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);
}
}
-> 2번 풀이로 뒤에서부터 구현하는거 했는데 j 조건문 쓰는게 헷갈려서 한참 걸렸다… 그냥 1번 풀이가 젤 쉬운듯함ㅠ
- 3번 풀이
- D[i] = A[i]에서 시작하는 가장 긴 감소하는 부분 수열의 길이
- D[i] = max(D[j]) + 1 (i < j && A[i] > A[j])
- A[i] / A[j] 이렇게 있을 때 A[j]부터 감소하는 어떤 수열에 앞에 A[i]를 붙어 감소하는 부분수열을 만든다. 가장 긴 걸 찾기 위해선 모든 A[j] 중 가장 긴걸 찾고, 그 길이는 D[j]에 있을 거고 앞에 하나(A[i])가 추가되니까 +1
- An을 구해야 An-1을 구할 수 있고 An-1을 구해야 An-2를 구할 수 있고… 뒤쪽의 답을 이용하는 방식. A[i]로 시작한다면 i가 N->1로 가며 해결됨.
가장 긴 바이토닉 부분 수열(11054번)
https://www.acmicpc.net/problem/11054
문제
- 수열 A가 주어졌을 때, 그 수열의 바이토닉 부분 수열 중 가장 긴 것을 구하는 문제
- 바이토닉 수열 : 어떤 수 Sk를 기준으로 S1 < S2 < … Sk-1 < Sk > Sk+1 > … SN-1 > SN을 만족
풀이
- i번째에서 끝나는 가장 긴 증가하는 부분수열의 길이 + i번째에서 시작하는 가장 긴 감소하는 부분 수열의 길이 - 1 (i번째가 중복 포함되니까)
import java.util.*;
public class Main {
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[] asc = new int[n+1];
int[] desc = new int[n+1];
for(int i=1; i<=n; i++) {
asc[i] = 1;
for(int j=1; j<i; j++) {
if(a[j]<a[i] && asc[i]<asc[j]+1) {
asc[i] = asc[j]+1;
}
}
}
for(int i=n; i>=0; i--) {
desc[i] = 1;
for(int j=i+1; j<=n; j++) {
if(a[i]>a[j] && desc[i]<desc[j]+1) {
desc[i] = desc[j]+1;
}
}
}
int ans = asc[1]+desc[1]-1;
for(int i=2; i<=n; i++) {
if(ans<asc[i]+desc[i]-1)
ans = asc[i]+desc[i]-1;
}
System.out.println(ans);
}
}
연속합2(13398번)
https://www.acmicpc.net/problem/13398
문제
- 수열의 연속합 중 가장 큰 합을 구하는 문제
- 수는 하나 제거할 수 있다. 제거하지 않아도 된다.
풀이
- 연속합 문제는 D[i] = A[i]에서 끝나는 최대 연속합, max(D[i-1]+A[i],A[i]), 시간복잡도 O(N)
- 연속합2는 연속합 풀이를 이용할 수 있는데, 일단 연속합을 구하고 하나씩 제거하고 제거한 연속합과 비교 -> 비효율적. O(N²) 시간제한 초과
- 가장 긴 바이토닉 부분 수열 아이디어를 이용한다.
- D[i] = i번째에서 끝나는 최대 연속합
- D2[i] = i번째에서 시작하는 최대 연속합
- i번째 수를 지웠을 때 변화하는 값은 연속합 중 i때문에 분리된 경우. 즉 i-1로 끝나는 연속합과 i+1 연속합이 이어진다. D[i-1] + D2[i+1]
- 1과 N번째는 제거할 필요가 없다. 연속합 구할때 알아서 처리되기 때문. 2≤i≤N-1
- D[i], D2[i], D[i-1] + D2[i+1] 각각 O(N)이 걸리고 O(N)+O(N)+O(N) = 최종시간복잡도 O(N)
import java.util.*;
public class Main {
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];
int[] d2 = new int[n+1];
//d[i] 구하기
for(int i=1; i<=n; i++) {
d[i] = a[i];
if(i>0 && d[i] < d[i-1] + a[i])
d[i] = d[i-1] + a[i];
}
//d2[i] 구하기
for(int i=n; i>=1; i--) {
d2[i] = a[i];
if(i<n && d2[i] < d2[i+1] + a[i])
d2[i] = d2[i+1] + a[i];
}
//ans 구하기
int ans = d[1];
for(int i=2; i<=n; i++) {
if(ans <= d[i])
ans = d[i];
}
for(int i=2; i<n; i++) {
if(ans < d[i-1]+d2[i+1])
ans = d[i-1] + d2[i+1];
}
System.out.println(ans);
}
}
타일채우기(2133번)
https://www.acmicpc.net/problem/2133
문제
- 3 x N을 1 x 2, 2 x 1로 채우는 방법의 수
풀이
- 2xN 사각형으로 끝에 가로 두개 D[n-2] + 끝에 세로 하나 D[n-1] 해서 풀었었음
- D[i] = 3 x i를 채우는 방법의 수
- 마지막에 올 수 있는 가능한 경우의 수
- D[i] = 3 x D[i-2] + 2 x D[i-4] + 2 x D[i-6] + 2 x D[i-8] + …
- 다이나믹 문제 풀때 모든 방법을 찾아야한다ㅠ 그래야 올바른 정답 구할 수 있음
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] d = new int[n+1];
d[0] = 1;
for(int i=2; i<=n; i+=2) {
d[i] = 3 * d[i-2]; // 3*d[i-2] 처리
for(int j=i-4; j>=0; j-=2) {
d[i] += d[j]*2; //d[i-4]부터 짝수에서 나오는 방법 수 더해주기
}
}
System.out.println(d[n]);
}
}
댓글남기기