[코딩테스트] 다이나믹 프로그래밍(1차원 다이나믹)
reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.
2xn 타일링(백준 11726번)
https://www.acmicpc.net/problem/11726
문제
- 2xn 직사각형을 1x2, 2x1타일로 채우는 방법의 수
- D[n] = 2xn 직사각형을 채우는 방법의 수
풀이
- 끝이 세로 직사각형으로 끝난다면 2 x (n-1) + 2 x 1 로 볼 수 있다 = 2 x n
- 끝이 가로 직사각형 두개로 끝난다면 2 x (n-2) + 1 x 2인 직사각형 두개 = 2 x n
- 2xn 을 채울 수 있는 방법을 D[n] 이라고 한다면 끝에 세로 놓는건 D[n-1], 가로는 D[n-2] 이 두가지밖에 없고 방법은 두 가지 경우를 합쳐줘야함.
- D[n] = D[n-1] + D[n-2]
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] memo = new int[n+1];
memo[0] = 1;
memo[1] = 1;
for(int i=2; i<=n; i++) {
memo[i] = memo[i-1]+memo[i-2];
memo[i] %= 10007;
}
System.out.println(memo[n]);
}
}
2xn 타일링2 (백준 11727번)
https://www.acmicpc.net/problem/11727
문제
- 2xn 직사각형을 1x2, 2x1, 2x2 타일로 채우는 방법의 수
- D[n] = 2xn 직사각형을 채우는 방법의 수
풀이
- 1번 문제처럼 2x1 세로 직사각형으로 끝나는 경우 D[n-1], 1x2 가로 직사각형 두개로 끝나는 경우 D[n-2] + 2x2가 가장 오른쪽에 오는 경우 D[n-2]
- D[n] = D[n-1] + D[n-2]x2
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] memo = new int[n+1];
memo[0] = 1;
memo[1] = 1;
for(int i=2; i<=n; i++) {
memo[i] = memo[i-1]+memo[i-2]*2;
memo[i] %= 10007;
}
System.out.println(memo[n]);
}
}
1, 2, 3 더하기 (백준 9095번)
https://www.acmicpc.net/problem/9095
문제
- 정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제
- n=4 이면 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1
풀이
- 가장 마지막에 사용한 수는 1,2,3 가 올 수 있다. 그 이전 상황을 알아봐야 함.
- 마지막이 1일 때 앞은 n-1 : 정수 n을 1,2,3의 합으로 나타내는 게 D[n]이니 마지막이 1일 경우엔 정수 n-1을 1,2,3의 합으로 나타내는 것과 같다. 즉 D[n-1]
- 마지막이 2일 때 앞은 n-2은 D[n-2], 마지막이 3일 때 n-3은 D[n-3]
- D[n] = D[n-1] + D[n-2] + D[n-3]
- D[0]은 문제 영역은 아니지만(1≤N≤10) D[0]을 정의해주면 이 문제를 더 편하게 풀 수 있다. 수를 0개 사용하는 방법 1가지 D[0] = 1
0 : 1
1 : D[0] = 1
2 : D[0] + D[1] = 1 + 1 = 2
3 : D[0] + D[1] + D[2] = 1+1+2 = 4 - 다이나믹 시간복잡도 : 전체 문제의 개수 x 문제 1개를 푸는 시간 = 0부터 n까지 n+1개 x D[n-1]+D[n-2]+D[n-3] = O(N) x O(1) = O(N)
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int s=0; s<t; s++) {
int n = sc.nextInt();
int[] memo = new int[11];
memo[0] = 1;
memo[1] = 1;
memo[2] = 2;
for(int i=3; i<=n; i++) {
memo[i] = memo[i-1]+memo[i-2]+memo[i-3];
}
System.out.println(memo[n]);
}
}
}
-> 나는 테스트 케이스마다 다시 만드는 방법인데 선생님은 n범위가 적으니까 먼저 집합 값을 다 구해놓고 밑에 출력을 테스트케이스만큼 반복하셨는데 이 방법이 훨씬 좋은듯…ㅠ 오늘도 배운다.. 반복문 구조도 좀 다름. 나는 0,1,2번째를 직접 값 넣어줬는데 선생님은 0번만 구하고 i와 j를 이용해서 j는 1~3이고 i-j>0 이라면 d[i] += d[i-j];로 구현하셨다.
카드 구매하기(백준 11052번)
https://www.acmicpc.net/problem/11052
문제
- 카드 N개를 구매해야 한다.
- 카드팩은 총 N가지 종류가 존재한다.
- i번째 카드팩은 i개의 카드를 담고 있고, 가격은 P[i] 이다.
- 카드 N개를 구매하는 비용의 최대값을 구하는 문제
풀이
- D[N] = 카드 N개를 구매하는 최대 비용
- 마지막에 구매한 카드팩에 카드가 몇 개 들어있었는지? 몇 번째 카드팩일까? 모른다. -> 모든 방법을 다 해봐야 한다.
- 마지막 구매 카드팩이 1번째 카드팩, 2번째 카드팩, …, n번째카드팩일 경우가 있다 가정했을 때
- 1번째 카드팩 : N-1개의 카드를 구매 + 1번째 카드팩 = D[n-1] + P[1]
- 2번째 카드팩 : N-2개의 카드를 구매 + 2번째 카드팩 = D[n-2] + P[2]
- n번째 카드팩 : 0개의 카드를 구매 + N번째 카드팩 = D[0] + P[n]
- n가지를 다 계산하고 이 중에 최대값을 구하기
- 앞 문제는 방법이 2개, 3개 이렇게 정해져있는데 이 문제는 가능한 방법의 개수가 전부 다름. 이럴땐 변수를 이용해 일반화 해주자.
- D[i] = 카드 i개 구매하는 최대 비용
- 마지막에 j번째 카드팩을 구매했다면 i-j의 카드를 이 전에 구매했어야 함.
- D[i] = max(D[i-j] + P[j])
- 식에 변수가 들어가면 변수의 범위 만들어 줘야함. 1≤j≤i
- 시간복잡도 : 전체 문제의 개수 N개 x 문제 1개를 푸는 시간은 점화식 복잡도 O(N) = O(N²)
- 점화식 복잡도 : j가 최대 몇 번까지 수행될 것인가? j범위 1부터 i, i 최대값은 n이니까 1부터 n까지 살펴보는 것 가능. 즉 O(N)
- D[0]개 구매하는 비용은 카드 구매하지 않는 것, D[0] = 0 초기값
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];
int[] p = new int[n+1];
for(int i=1; i<=n; i++) {
p[i] = sc.nextInt();
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=i; j++) {
if(d[i]<d[i-j]+p[j])
d[i] = d[i-j]+p[j];
}
}
System.out.println(d[n]);
}
}
카드 구매하기 2 (백준 16194번)
https://www.acmicpc.net/problem/16194
문제
- 카드 N개를 구매해야 한다.
- 카드팩은 총 N가지 종류가 존재한다.
- i번째 카드팩은 i개의 카드를 담고 있고, 가격은 P[i] 이다.
- 카드 N개를 구매하는 비용의 최솟값을 구하는 문제
풀이
- 위 문제의 max를 min으로 바꿔주기
- D[i] = min(D[i-j] + P[j])
- 카드 구매하기는 카드구매비용은 음수가 나오지 않기에 d[i]≥0, 별도의 처리 없이 정답 구할 수 있음. 하지만 최소는 P[i]≥1 니까 D[i]≥1
- 그래서 배열 d 초기값을 0이 아닌 다른 값을 설정해줘야 한다.
- 매우 큰 값 넣어주기
d[i] = 1000*10000;카드의 개수 N≤1000, 카드팩의 가격 ≤10,000이기 때문에 - 또는
d[i] = -1;처럼 음수를 다 넣어주기, -1은 아직 정답을 구하지 않았다는 의미임.
- 매우 큰 값 넣어주기
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];
int[] p = new int[n+1];
for(int i=1; i<=n; i++) {
p[i] = sc.nextInt();
d[i] = 1000*10000;
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=i; j++) {
if(d[i]>d[i-j]+p[j])
d[i] = d[i-j]+p[j];
}
}
System.out.println(d[n]);
}
}
-> d[i]에 매우 큰 값 넣어주는 방식으로 풀었다
댓글남기기