[코딩테스트] 다이나믹 프로그래밍(연속과 관련된 다이나믹)
reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.
1,2,3 더하기 5 (백준 15990번)
https://www.acmicpc.net/problem/15990
문제
- 정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제
- 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.
- n = 4, 1+2+1, 1+3, 3+1
풀이
- 점화식을 그대로 못쓸 때 좋은 방법은 점화식에 그 조건을 넣어버리는 것
- 점화식에 추가해야 하는 값 : 마지막에 어떤 수를 사용했는지
- D[n] = D[n-1] + D[n-2] + D[n-3] 가 원래 점화식이고 D[i] = i를 만드는 방법의 수라면
- D[i][j] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j
- +1 = i 면 D[i][1], 1앞엔 i-1 인데 1이 들어올 수 없다 즉 D[i][1] = D[i-1][2] + D[i-1][3]
- +2 = i는 D[i][2] = D[i-2][1] + D[i-2][3]
- +3 = i는 D[i][3] = D[i-3][1] + D[i-3][2]
- 정답 : D[n][1] + D[n][2] + D[n][3]
- 이전 1,2,3 더하기에서 사용한 초기화 D[0] = 1 즉 0을 만드는 방법은 수 0개를 사용하는 방법 하나는 여기서 사용할 수 없음, 수 0개라면 마지막에 사용한 수가 없기 때문임. 또한 D[0][1] = 1, D[0][2] = 1, D[0][3] = 1 로 초기화 하면 D[i][1] = D[i-1][2] + D[i-1][3]기 때문에 D[1][1] = D[0][2] + D[0][3] = 2 로 중복이 발생하게 됨.
- D[1][1] = 1, D[2][2] = 1, D[3][3] = 1 이렇게 해주고 나머지에 대해서만 위 식을 이용해줘야 한다.
import java.util.*;
public class Main {
public static void main(String args[]) {
final long mod = 1000000009;
final int limit = 100000;
long d[][] = new long[limit+1][4];
for(int i=1; i<=limit; i++) {
if(i-1>=0) {
d[i][1] = d[i-1][2] + d[i-1][3];
if(i==1) {
d[i][1] = 1;
}
}
if(i-2>=0) {
d[i][2] = d[i-2][1] + d[i-2][3];
if(i==2) {
d[i][2] = 1;
}
}
if(i-3>=0) {
d[i][3] = d[i-3][1] + d[i-3][2];
if(i==3) {
d[i][3] = 1;
}
}
d[i][1] %= mod;
d[i][2] %= mod;
d[i][3] %= mod;
}
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i=0; i<t; i++) {
int n = sc.nextInt();
System.out.println((d[n][1]+d[n][2]+d[n][3])%mod);
}
}
}
쉬운 계단 수 (백준 10844번)
https://www.acmicpc.net/problem/10844
문제
- 인접한 자리의 차이가 1이 나는 수를 계단 수라고 한다. ex)45656
- 길이가 N인 계단 수의 개수를 구하는 문제
풀이
- 인접한 자리의 차이 = 연속한 자리의 차이 = 마지막 수가 무엇인지
- D[n] = 길이가 n인 계단 수로 처리하면 연속처리 할 수 없음
- D[i][j] = 길이가 i인 계단 수, 마지막 자리가 j인 계단 수의 개수
- D[i][j] = D[i-1][j-1] + D[i-1][j+1]
- D[i][j]를 계단수와 j(j는 i번째 자리) 로 나눈다고 하면 계단수의 길이는 i-1이고 계단수의 마지막 자리는 i-1번째 자리이다. 마지막 자리는 i번째 자리가 j기에 j-1 거나 j+1
- 하지만 j=0 인 경우는? j-1 이 성립하지 않음. 따라서 1≤j≤8 일때만 성립하는 식임
- j=0 일땐 D[i-1][j+1], j=9일땐 D[i-1][j-1]
- 정답 : D[N][0] ~ D[N][9] 까지의 합
- 초기화, 마지막 수가 필요하기에 길이 0인건 정의할 수 없다. 길이가 1인 경우 D[1][1] = D[1][2] = D[1][9] = 1 로 초기화. 단, D[1][0] 은 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][10];
long mod = 1000000000;
d[1][0] = 0;
for(int i=1; i<=9; i++) {
d[1][i] = 1;
}
for(int i=2; i<=n; i++) {
for(int j=0; j<=9; j++) {
if(j>=1)
d[i][j] += d[i-1][j-1];
if(j<9)
d[i][j] += d[i-1][j+1];
d[i][j] %= mod;
}
}
long ans = 0;
for(int i=0; i<=9; i++) {
ans += d[n][i];
}
ans %= mod;
System.out.println(ans);
}
}
-> % mod를 해주는 이유는 memo[n][i]가 1~9까지 반복해 더하다 보면 10억을 넘어갈 수 있기 때문이라고 함!
이친수 (백준 2193번)
https://www.acmicpc.net/problem/2193
문제
- 0과 1로만 이루어진 수를 이진수라고 한다.
- 다음 조건을 만족하면 이친수라고 한다.
- 이친수는 0으로 시작하지 않는다.
- 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
- N자리 이친수의 개수를 구하는 문제
풀이
- D[i][j] = 길이가 i 마지막 수가 j인 이친수의 개수, j = 0,1
- D[i][0] = 길이가 i 인데 마지막 수가 0, 마지막 수 앞의 길이는 i-1, i-1엔 0과 1 둘 다 들어갈 수 있다.
D[i][0] = D[i-1][0] + D[i-1][1] - D[i][1] = 길이가 i 인데 마지막 수가 1, 마지막 수 앞의 길이는 i-1, i-1엔 오직 0만 가능하다.
D[i][1] = D[i-1][0] - 이친수는 0으로 시작하지 않는 건 초기화로 설정 가능. D[1][0] = 0, 반면에 D[1][1] = 1
- 1차원으로도 해결할 수 있다. 가능한 경우가 0으로 끝나는 경우, 1로 끝나는 경우 두가지밖에 없기 때문임.
- D[i] = i자리 이친수라고 하면 끝에 0이 오는 경우 / 1이 오는 경우 두 개 있음.
- 0일 경우 0,1 둘 다 올 수 있으니 D[i-1]
- 1일 경우 0만 옴. 1차원 다이나믹으로도 풀 수 있는 이유는 0,1만 있기 때문임. 01을 하나로 보면 i-2 뒤에 01을 붙였다고도 볼 수 있음. D[i-2]
- D[i] = D[i-1] + D[i-2]
- 초기화 : 1앞엔 반드시 0이 와야 한다. 그렇지 않은 경우가 1만 있는 경우. D[1] = 1
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] d = new long[n+1];
d[1] = 1;
if(n>=2) {
d[2] = 1;
}
for(int i=3; i<=n; i++) {
d[i] = d[i-1] + d[i-2];
}
System.out.println(d[n]);
}
}
-> 1차원으로 풀었는데 d가 long형 배열이 아니면 오류난다ㅠㅠ 수 범위는 어떻게 예측하고 푸는거지…하고 찾아봤는데 피보나치 수는 46항부터 int 범위를 초과한다고 한다. 기억해두자.
댓글남기기