[코테]15-연속과 관련된 다이나믹

1,2,3 더하기 5 (15990)

원래 1,2,3더하기에서 점화식은 아래와 같다.
D[n]=n을 만드는 방법의 수 =D[n-1]+D[n-2]+D[n-3]
하지만, 여기서는 같은 수를 두 번 이상 연속해서 사용하면 안되기 때문에 해당 식을 쓸 수 없다.

이런 경우에 사용하는 방법
1. 그 조건을 점화식에 넣어본다.

D[i]=i를 만드는 방법의 수
D[i][j]=i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j

( i-1을 만듦 +1,+2,+3중에 +1은 제외) +1 = i
-> D[i][1]=D[i-1][2] + D[i-1][3]
( i-2를 만듦. +1과 +3만 사용) +2 = i
-> D[i][2] = D[i-2][1] + D[i-2][3]
( i-3을 만듦. +1과 +2만 사용) +3 = i
-> D[i][3] = D[i-3][1] + D[i-3][2]

D[i][j]= i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j.

D[0]=1로 초기화한다면 중복이 발생한다.
D[0][1]=2, D[0][2]=2,D[0][3]=1로 초기화를 했다면
D[1][1] = D[0][2] + D[0][3] = 2(중복이 발생하기 됨)
따라서, 예외 처리를 해야한다.

import java.util.*;

public class Main {
	static final long mod = 1000000009L;
	static long d[][] = new long[100001][4];
		
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		for(int i=1;i<d.length;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;
		}
		
		int t = sc.nextInt();
		for(int k=0;k<t;k++) {
			int n=sc.nextInt();
			System.out.println((d[n][1]+d[n][2]+d[n][3])%mod);
		}
	}
}

쉬운 계단 수(10844)

인접한 자리의 차이가 1이 나는 수를 계단 수라고 한다.
예: 45656
길이가 N인 계단 수의 개수를 구하는 문제.

• 인접한 자리의 차이 = 연속하는 수의 차이와 같다.

D[i][j] = 길이가 i인 계단수, 마지막 자리가 j인 개수
D[i][j] = D[i-1][j-1] + D[i-1][j+1]
-> 맨 마지막수는 j의 -1이거나 +1인 값만 올 수 있음.
만약, j=0인 경우 j-1은 -1임.
그래서 모든 경우의 수에는 사용가능 x
(1<=j<=8)
j=0, D[i-1][j+1]
j=9, D[i-1][j-1]

정답: D[n][0]부터 D[n][9].

• D[1][0] = 0.

import java.util.*;

public class Main {
	static final long mod =  1000000000L;

	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=1;i<=9;i++) {
			d[1][i] = 1;
		}
		
		for(int i=2; i<=n; i++) {
			for(int j=0; j<10; j++) {
				d[i][j] = 0;
				if(j-1 >= 0) {
					d[i][j] += d[i-1][j-1];
				}
				if(j+1 <=9) {
					d[i][j] += d[i-1][j+1];
				}
				d[i][j] %= mod;
			} 
		}
		
		long res=0;
		for(int i=0;i<10;i++) {
			res += d[n][i];
		}
		
		res %= mod;
		System.out.println(res);
	}
}

이친수

0과 1로만 이루어진 수를 이진수라고 한다.
다음 조건을 만족하면 이친수라고 한다.
1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서 1이 두 번 연속으로 나타나지 않는다. 즉 11을 부분 문자열로 갖지 않는다.
N자리 이친수의 개수를 구하는 문제.

• D[i][j] = 길이가 i, 마지막 수가 j인 이친수의 개수. (j=0,1)
  D[i][0]과 D[i][1] 따로따로 구해봄.

• 길이가 i인데 마지막 수가 0인 경우

• 길이가 i인데 마지막 수가 1인 경우
  D[i][0] =D[i-1][0] + D[i-1][1]
  D[i][1] = D[i-1][0]

이친수는 0으로 시작하지 않는다 => 처리방법 : 초기화.

• 가장 길이가 작은 길이는 1임. D[1][0]= 0. D[1][1] = 1.

• 1차원 배열으로도 가능함. 0과 1밖에 없기 때문에.

• D[i] = i자리 이친수.
• 가장 마지막에 0이 오는경우, 1이 오는 경우가 있음.
• 마지막 자리가 1이되면 무조건 그 앞은 0이 와야함.

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]);
	}
}

최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.