[코딩테스트] 다이나믹 프로그래밍(제곱수의 합부터 퇴사까지)

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

가장 긴 증가하는 부분 수열(1699번)

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

문제

• 주어진 자연수 N을 제곱수들의 합으로 표현할 때 그 항의 최소개수를 구하는 문제

풀이

• 1,2,3 더하기 문제와 매우 유사, 제곱수 사용해 구한 N의 최소 개수 구하면 됨
• D[N] = N을 제곱수의 합으로 나타낼 때의 항의 최소 개수
• i² 전의 합은 N-i² 이며 최소 개수는 D[N-i²]임
• D[N] = min(D[N-i²]+1)
• 1≤i²≤N 이니까 i≤√n과 같아서 하나의 값을 구하는데 걸리는 시간 √n 따라서 O(N x √n)

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

		for(int i=1; i<=n; i++) {
			d[i] = i;
			for(int j=1; j*j<=i; j++) {
				if(d[i] > d[i-j*j]+1) {
					d[i] = d[i-j*j]+1;
				}
			}
		}
		System.out.println(d[n]);
	}
}

-> 풀이만 알면 코드를 짜는건 간단한데 아직 딱 문제만 보고 dp사고를 하는게 쉽지가 않다… 여러 문제를 풀어보자ㅠㅠㅠㅠㅠ

합분해(2225번)

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

문제

• 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수

풀이

• 1,2,3 더하기 문제와 유사
• D[k][n] = 정수 k개를 더해 그 합이 n이 되는 경우의 수
• 마지막엔 l이 온다고 했을 때, l이 없으면 앞쪽은 k-1개, 합은 n-l
• D[k-1][n-l] + l = N, l의 범위는 0≤l≤n
• D[k][n] = ∑ D[k-1][n-l]
• 전체 문제 시간: kn, 하나 구하는데 시간: 0(N), O(kn²), dp에서 전체문제 개수는 Memoization 배열의 크기와 대부분 같다
• 초기화 수 0개, 합 0개 d[0][0] = 1

import java.util.*;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		final long mod = 1000000000L;
		int n = sc.nextInt();
		int k = sc.nextInt();
		long[][] d = new long[k+1][n+1];
		d[0][0] = 1; //초기화
		for(int i=1; i<=k; i++) {
			for(int j=0; j<=n; j++) {
				for(int l=0; l<=j; l++) {
					d[i][j] += d[i-1][j-l];
					d[i][j] %= mod;
				}
			}
		}
		System.out.println(d[k][n]);
	}
}

퇴사(14501번)

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

문제

• N+1일이 되는 날 퇴사를 하려 한다(1≤N≤15)
• 남은 N일 동안 최대한 많은 상담 하려 함.
• 하루에 하나의 상담 할 수 있고 i일에 상담 하면 T[i]일이 걸리고 P[i]원을 번다

풀이

• 브루트 포스로 풀었던 문제, O(2²) 걸렸었음
• 4일이 된 경우 전체 정답 (1~3일까지 상담한 수익)+(4~6일까지 상담한 수익), 즉 1~3일은 최대값만 알면 됨
• 큰 문제의 정답을 작은 문제에서 구할 수 있고, 작은 문제 정답은 언제나 일정하기 때문에 dp를 이용해서 풀 수 있음

import java.util.*;

public class Main {
	static int n;
	static int[] t;
	static int[] p;
	static int[] d;
	static int ans = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		t = new int[n+1];
		p = new int[n+1];
		d = new int[n+1];
		for (int i = 1; i <= n; i++) {
			t[i] = sc.nextInt();
			p[i] = sc.nextInt();
			d[i] = -1;
		}
		System.out.println(go(1));
	}

	private static int go(int day) {
		if(day==n+1) { //날짜가 퇴사일 됐을때
			return 0;
		}
		if(day>n+1) { //날짜가 퇴사일 넘었을때
			return -100000000;
		}
		if(d[day]!=-1) { //초기값이 아닐때 저장된 값 출력
			return d[day];
		}

		int t1 = go(day+1); //상담 안했을때
		int t2 = p[day] + go(day+t[day]); //상담 했을때
		d[day] = Math.max(t1, t2); //memorization 배열에 최대값 저장
		return d[day];
	}
}

-> 이거 브루트포스 재귀로 할때도 한참 걸렸었는데… dp방법 코드 이해하는게 더 어려운거 같다…ㅠㅠ dp 문제는 진짜 많이 풀고 익숙해져야 할거같다