[코딩테스트] 다이나믹 프로그래밍(오르막 수까지)

reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.

1,2,3 더하기 3 (15988번)

https://www.acmicpc.net/problem/15988

문제

• 정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제(n≤1,000,000)

풀이

• 1,2,3 더하기에서 n의 범위가 더 많아진 문제
• D[n] = D[n-1] + D[n-2] + D[n-3]
• 문제에서 10억9로 나눈 나머지를 구하라 했음. 그럼 d[i-1], d[i-2], d[i-3]에 들어갈 수 있는건 각각 최대 10억팔임. 그럼 합이 30억24인데 int 최대는 21억임. 따라서 int로 풀고 싶다면 각각 d[i]%mod 를 해줘야 함.
• dp는 이전 값이 항상 일정하기 때문에 테스트케이스마다 그 값을 다시 구하는건 무의미함. 처음부터 다 구해놓고 밑에서 입력받고 계산하기. 매번 다시 구하면 시간초과가 난다.

import java.util.*;

public class Main {
	static final int limit = 1000000;
	static final int mod = 1000000009;
	public static void main(String[] args) {
		long d[] = new long[limit+1];
		d[0] = 1;
		for(int i=1; i<limit; i++) {
			for(int j=1; j<=3; j++) {
				if(i-j >= 0) {
					d[i] += d[i-j];
				}
			}
			d[i] %= mod;
		}

		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while(t-->0) {
			int n = sc.nextInt();
			System.out.println(d[n]);
		}
	}
}

-> 이전에 1,2,3 풀었을 때 나는 테스트케이스마다 다시 값을 구하는 방식으로 풀고 반성했었는데 이번엔 백준 선생님이 푸신 방법대로 했다. dp는 이전 값이 일정하기 때문에 다시 구하는 건 비효율적이라는 걸 기억하자.

RGB 거리 (1149번)

https://www.acmicpc.net/problem/1149

문제

• RGB 거리에 사는 사람들은 집을 빨강, 초록, 파랑 중에 하나로 칠하려고 한다
• 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다
• 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다.
• 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 문제

풀이

• 0 빨강, 1 초록, 2 파랑
• A[i][j] : i번 집을 j번 색으로 칠하는 비용
• 집 i를 i-1과 색이 다르게 칠하면 모든 이웃은 같은 색으로 칠할 수 없다!, 연속 dp 문제
• D[i][j] = i번 집을 색 j로 칠했을 때, 1~i번 집을 칠하는 비용의 최소값
• D[i][0] = min(D[i-1][1] + D[i-1][2]) + A[i][0]
• 정답 : min(D[n][0], 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[][] home = new int[n+1][3];
		int[][] d = new int[n+1][3];
		for(int i=1; i<=n; i++) {
			for(int j=0; j<=2; j++) {
				home[i][j] = sc.nextInt();
			}
		}
		for(int i=1; i<=n; i++) {
			d[i][0] = Math.min(d[i-1][1],d[i-1][2]) + home[i][0];
			d[i][1] = Math.min(d[i-1][0],d[i-1][2]) + home[i][1];
			d[i][2] = Math.min(d[i-1][0],d[i-1][1]) + home[i][2];
		}
		System.out.println(Math.min(d[n][0], Math.min(d[n][1], d[n][2])));
	}
}

-> dp 조금씩 감이 잡히는 거 같다! 풀이 듣기 전에 풀이법 생각해내서 뿌듯했음..

동물원 (1309번)

https://www.acmicpc.net/problem/1309

문제

• 가로로 두 칸, 세로로 N칸인 동물원이 있다
• 가로, 세로를 붙어 있게 배치하면 안 된다
• 가능한 배치의 수

풀이

• D[n] = 세로로 n칸인 동물원이 동물 배치하는 수
• 가로일때 둘 다 들어있을 경우만 없으면 됨, 세로 역시 가로를 한 번에 배치한다고 하면 해결됨. 즉 마지막 동물배치에 따라 위 배치가 달라지니다.
• D[n][m] = 세로로 n칸인 동물원 배치의 수, 마지막 칸은 m번 방법을 사용. 윗 칸의 방법을 다 구해주자!
• D[n][0] = n번 줄에 배치하지 않음
• D[n][1] = n번 줄에 왼쪽에만 배치함
• D[n][2] = n번 줄에 오른쪽에만 배치함
• D[n][0] = D[n-1][0] + D[n-1][1] + D[n-1][2]
  D[n][1] = D[n-1][0] + D[n-1][2]
  D[n][2] = D[n-1][0] + D[n-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][3];
		d[0][0] = 1;
		for(int i=1; i<=n; i++) {
			d[i][0] = (d[i-1][0] + d[i-1][1] + d[i-1][2])%9901;
			d[i][1] = (d[i-1][0] + d[i-1][2])%9901;
			d[i][2] = (d[i-1][0] + d[i-1][1])%9901;
		}
		System.out.println((d[n][0]+d[n][1]+d[n][2])%9901);
	}
}

-> 이 문제 역시 [i][0],[i][1],[i][2] 값마다 % 를 안해주면 int값을 넘기 때문에 꼭 %처리를 해주자…!

오르막 수 (11057번)

https://www.acmicpc.net/problem/11057

문제

• 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다
• 인접한 수가 같아도 오름차순으로 친다
• 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 문제
• 수는 0으로 시작할 수 있다 ex) 1233345, 357, 8888888, 1555999

풀이

• 쉬운계단수와 매우 비슷. 쉬운계단수는 인접한 자리의 차이 1, 이 문제는 인접 자리가 오름차순 만족
• D[i][j] = 수의 길이는 i, 마지막(i번째) 수는 j인 오르막 수의 개수
• i번째에 j가 있고 i-1번째엔 뭐가 올지 모르니 k라고 변수 지정, 단 k≤j
• D[i][j] = ∑D[i-1][k] (0≤k≤j)
• 초기화 D[0][0] = 1 로 해도 됨. 계단수는 0부터 시작하는 경우가 있어서 D[1][0] = 0, D[1][1]~D[1][9] = 1로 초기화 후 2로 시작했음. 오르막 수는 가장 작은 건 길이 1이고 마지막 수 0~9 수이기 때문에 D[1][i] = 1인데, D[0][0]=1로 해두면
  • D[1][0] = D[0][0] = 1
  • D[1][1] = D[0][0] + D[0][1] = 1+0 = 1
  • D[1][2] = D[0][0] + D[0][1] + D[0][2] = 1+0+0 = 1
  • 이렇게 되기 때문에 D[0][0] = 1 만 해주고 i≥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][10];
		d[0][0] = 1;
		for(int i=1; i<=n; i++) {
			for(int j=0; j<=9; j++) {
				for(int k=0; k<=j; k++) {
					d[i][j] += d[i-1][k];
					d[i][j] %= 10007;
				}

			}
		}
		long ans = 0;
		for(int i=0; i<10; i++) {
			ans += d[n][i];
		}
		ans %= 10007;
		System.out.println(ans);
	}
}

-> 이제 처음 dp접했을 때와 달리 얼추 문제보고 어떻게 하면 될 것 같다~는 감은 오는데 초기화를 d[0][0] = 1만 해줘도 된다거나… 이런 세세한 부분에서 좀 막히는 것 같다. 얘도 꾸준히 하다보면 늘겠지..