2 x n 타일링
2 x n 직사각형을 1 x 2, 2 x 1 타일로 채우는 방법의 수
아래 그림은 2 x 5를 채우는 방법의 수
D[n] = 2 x n 직사각형을 채우는 방법의 수
- 가장 오른쪽에 올 수 있는 타일의 모양은 2가지 밖에 존재하지 않음.
- 2 x n 직사각형이 있을 때, 가장 오른쪽에 타일을 놓을 수 있는 방법은 총 2가지.
- 2 x n = D[n]
- 2 * n-1 = D[n-1]
- 2 * n-2 = D[n-2]
D[n] = D[n-1] + D[n-2]
2 x n 타일링 2
2 x n 직사각형을 1 x 2, 2 x 1, 2 x 2 타일로 채우는 방법의 수
D[n]= 2 x n 직사각형을 채우는 방법의 수
-
가장 오른쪽에 올 수 있는 것 : D[N-1] , D[N-2], D[N-2]
-
D[N] = D[N-1] + D[N-2] * 2
=> 식이 이렇게 나오기 때문에, 위의 코드에서 식만 살짝 바꿔주면 된다. -
가장 마지막 단계가 무엇인지를 보고 그게 없을때의 경우의 수를 생각해봄.
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[1001];
d[0] = 1;
d[1] = 1;
for(int i=2;i<=n;i++) {
d[i] = d[i-1]+d[i-2]*2;
d[i] %= 10007;
}
System.out.println(d[n]);
}
}1,2,3 더하기
예전에 풀었던 문제인데, 다이나믹 프로그래밍 방식으로 다시 풀이
정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제
여기서, 정수 n을 1,2,3의 합으로 나타내는 방법의 수를 D[n]이라고 표시함.
문제에서 1,2,3의 합이라고 나타내라고 했으니까 가장 마지막에 오는 수는
1이 올수도, 2가 올수도, 3이 올수도 있다.
만약 맨 뒤에 1이 온다면 그 앞에서 n-1을 만들고 +1을 해서 n을 만든 것.
만약 맨 뒤에 2가 온다면 그 앞에서 n-2를 만들고 +2를 해서 n을 만든 것.
만약 맨 뒤에 3이 온다면 그 앞에서 n-3을 만들고 +3을 해서 n을 만든 것.
-> n-1을 만드는 모든 방법의 수 (D[n-1]) 에 +1을 붙이면 n이 되는 것.
n-2를 만드는 모든 방법의 수 (D[n-2]) 에 +2를 붙이면 n이 되고,
n-3을 만드는 모든 방법의 수 (D[n-3]) 에 +3을 붙이면 n이 된다.
- D[n]=D[n-1]+D[n-2]+D[n-3].
- D[0]을 정의해주면 편하게 코딩이 가능함.
- 수를 0개 사용하는 경우 1가지 -> D[0]=1.
전체 문제의 개수 X 문제 1개를 푸는 시간.
점화식D[n]은 문제 1개를 푸는 식임.
D[n]=D[n-1]+D[n-2]+D[n-3]의 시간복잡도는 O(1) * N = O(N)임.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int d[]=new int[11];
d[0]=1;
for(int i=1;i<=10;i++) {
for(int j=1;j<=3;j++) {
if(i-j >= 0) {
d[i] += d[i-j];
}
}
}
int t= sc.nextInt();
for(int k=0;k<t;k++) {
int n= sc.nextInt();
System.out.println(d[n]);
}
}
}
카드 구매하기
카드 N개를 구매해야 한다.
카드팩은 총 N가지 종류가 존재한다.
i번째 카드팩은 i개의 카드를 담고 있고, 가격은 P[i]원이다.
카드 N개를 구매하는 비용의 최대값을 구하는 문제
- 카드팩, 카드팩, 카드팩 = N을 만듬
D[N] = 카드 N개를 구매하는 최대 비용. - 마지막에 어떤 카드팩을 구매했더니 카드가 N개가 되었음.
- 마지막 카드팩은 카드가 몇개 ? 몇번째 카드팩일까 ? 정답은 모른다,,
- 모른다는 정보는 다이나믹 프로그래밍에서 중요한 정보임.
- 모르는 경우에는 모든 방법을 다 동원해야함.
- 1번째 카드팩 = N개..
- 2번째 카드팩 = N개
............. - N번째 카드팩 = N개
=> 가장 마지막에 올 수 있는 경우의 수가 N가지가 있으면,
전부 계산해보고 최대값을 구하면 됨.
- 여기서 문제는 최대 비용을 구하는 것이기때문에 최대 비용만 구하면 됨.
- D[i]= 카드 i개 구매하는 최대 비용.
- N-1개의 카드를 구매 D[N-1] , 1번째 카드팩을 구매 P[1] 해서 N개를 만들었음.
=> D[N-1] + P[1]
N-2개의 카드를 구매 D[N-2] 2번째 카드팩을 구매 P[2] 해서 N개를 만듬.
=> D[N-2] + P[2]
...
N번째 카드팩을 구매하고 0개의 카드를 구매해서 N개를 만듬.
=> D[0]+P[N]
-
i개의 카드를 구매.
(i-j) 개의 카드를 구매한 상황에 -> j번째 카드팩을 만들어서 i개의 카드.
-> max( D[i-j] -> P[j] ) = Di -
시간복잡도
-
전체 문제의 개수 * 문제 하나를 푸는데 걸리는 시간.
-
N * O(N) = O(N^2)
-
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 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=1;i<=n;i++) {
for(int j=1;j<=i;j++) {
if(d[i] < d[i-j] + a[j]) {
d[i] = d[i-j] + a[j];
}
}
}
System.out.println(d[n]);
}
}
카드 구매하기 2
카드 N개를 구매하는 비용의 최소값을 구하는 문제.
max가 아니라 min으로 바꿔주면 됨.
이 방법은 배열d에 항상 0이 들어간다.
카드를 구매하는 비용은 0보다 크기 때문에, min의 결과는 항상 0이다.
따라서 초기값을 잘 설정해야한다.
- 값을 매우 큰 값을 넣어줌. 가능한 정답중 최대값을 넣어준다. (1000*10000)
- 음수를 넣어준다. (-1을 넣어줌)
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=1;i<=n;i++) {
d[i]=-1;
for(int j=1;j<=i;j++) {
if(d[i]==-1 || d[i] > d[i-j] + a[j]) {
d[i] = d[i-j] + a[j];
}
}
}
System.out.println(d[n]);
}
}최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.
