Computer Basis/Algorithms
[Algorithms] 백준 DP 문제모음 (bottom-up 유형)
DevPing9_
2021. 11. 1. 20:21
# 이친수 (2193번)
1. 곱셈 연산이나, 덧셈 연산은 큰 수 끼리 연산 수행 시 overflow 가 발생할 수 있음을 유의!!!!! (매우매우 중요)
- 저번에도 당하고 또 당하는 단골문제...
import java.util.Scanner;
public class Main{
// not starting with 0
// no serial 1
// how many binary with condition above, on size N
// 1<=n<=90 => dfs... Time Complexity(2^90)
// recurrence relation?
// f(n) = f(n-2) (starting with 1)
// + f(n-3) (starting with 0)
// + f(n-4) (starting with 00) .........?
// f(1) = 1, f(2) = 1, f(3) =2 , f(4) = 3, f(5)=5 ,f(6)=8
// f(4) = 1 + 0 + f(2) !!!!!!!!!!?
// f(4) = 1000,
// 1010, f(2)
// 1001, f(1)
// f(5) = 10000,
// 10100, 10101, (f(3))
// 10010,(f(2))
// 10001 (f(1))
// f(6) = 100000,
// 101000, 101010, 101001,(f(4))
// 100100, 100101,(f(3))
// 100010, (f(2))
// 100001, (f(1))
// .... f(n) = f(n-2)+f(n-3)+... + 1
// .... f(n-2) = f(n-4) + f(n-5)+ ... + 1
// dp(n) = dp(n-2) + f(n-3)+ f(n-2)
// f(6) = f(4)_...f(1) + 1 = 8
// f(7) = f(5)+...f(1) + 1 = f(5)+f(4) =13
// f(8) = f(6)+...f(1) + 1 = (f5)+(f6) = 21
// f(9) = f(7)+...f(1) + 1 = (f8)+(f7) = 34
// f(10) = f(9)+f(8) = 55
public static long dp[];
public static long f(int n){
if(n==1 || n==2 ) return dp[n]=1;
else if(n==3) return dp[n]=2;
else if(dp[n]!=0) return dp[n];
return dp[n]=f(n-1)+f(n-2);
}
// O(n^2)
public static int getCount(int n){
if(n <4){
if(n == 3) return 2;
return 1;
}else{
int sum=0;
for(int i=n-2; i>=1; i--){
sum+=getCount(i);
}
//f2, f1
return sum+1;
}
}
public static void printArr(int size){
for(int i=0;i<=size;i++){
System.out.print(dp[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
dp= new long[n+1];
System.out.println(f(n));
// printArr(n);
}
}# 연속합 (1912번)
1. 배열없이 하나의 단일 값을 dp 의 memoization 으로 사용
2. BufferedReader 사용하면, 메모리와 수행속도에 엄청난 차이가...!
import java.util.Scanner;
public class Main{
static long[] arr;
//serial sum maximum
//1<= n <=100_000
static long sum=0;
static long best=0;
//O(n^2)
public static void sumOfSubset(int size){
for(int i=0; i<size; i++){
sum=Math.max(arr[i],sum+arr[i]);
best=Math.max(best,sum);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
arr = new long[n];
for(int i=0; i<n; i++){
arr[i]=sc.nextInt();
}
/* BufferedReader 가 속도와 메모리에서 훨씬 성능을 압도한다.... 훔 ...
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
arr = new long[n];
StringTokenizer st = new StringTokenizer(br.readLine());
br.close();
for(int i=0; i<n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
*/
best = arr[0];
sumOfSubset(n);
System.out.println(best);
}
}# 쉬운 계단 수 (10844번)
1. 점화식찾아서 기뻐했는데 하하... 뺄셈이라 숫자가 커져서 MOD로 뭐 어쩌할 도리가없다...
* MOD로 나눠서 리턴하는 경우 뺄셈이 절대 들어가면 안된다.
2. MOD로 나눠서 리턴하는 경우, 모두 덧셈으로 치환 해주자!
# 성공한 코드
- O(n) 이긴 하지만 뭔가 찝찝하다..
- 1등 코드를 보니, N이 최대 100밖에 되지 않아, 100*10 의 2차원 전역변수를 사용했다. (로직은 같다. 휴.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
//1<=N<=100
//ans = ans % 1_000_000_000
//01 (x)
//10,12
//21,23
//32,34
//43,45
//...
//87,89
//98, -17 ... uhm.....
//1~8 은 다음자리에 2개의 수를 뽑을 수 있고,
//9는 다음자리에 1개의 수만 뽑을 수 있다.
//010,012 (x) = 2
//101,121,123 = 3
//210,212, 232,234 = 4
//321,323, 345,343
//767,765, 789,787 = 4
//876,878, 898 = 3
//989,987 = 2
//N=4..
//0101, 0121, 0123 (1로시작하는 경우의 수)
//case 0 : 1*3(case1)+ =3 // 1*2(case9)
//case 1 : 1*2(case0)+ 1*4(case2) =6
//case 2 : 1*3(case1) + 1*4(case3) =7
//case 3 : 1*4(case4) + 1*4(case2) = 8
//case 4 : 1*4(case5) + 1*4(case3) = 8
// ...
//case 7 : 1*4(case6) + 1*3(case8) = 7
//case 8 : 1*4(case7) + 1*2(case9) =6
//case 9 : 1*3(case8) + // 1*2(case0)
//대칭이네?
static long[] CASE;
static long[] copied_CASE;
static long MOD = 1_000_000_000;
static void CASE_UPDATE(){
copied_CASE = CASE.clone();
CASE[0] = copied_CASE[1];
CASE[9] = copied_CASE[8];
for(int i=1;i<=8;i++){
CASE[i] = (copied_CASE[i-1]+copied_CASE[i+1]) % MOD;
}
}
static void find(int n){
for(int i=2;i<=n;i++){
CASE_UPDATE();
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
CASE = new long[10];
copied_CASE = new long[10];
for(int i=0;i<10;i++){
CASE[i]=1;
}
find(n);
long sum=0;
for(int i=1; i<10; i++){
sum=(sum+CASE[i])%MOD;
}
System.out.println(sum);
}
}
# 뺄셈이 섞여서 실패한 코드
/* 점화식 코드... MOD로 나눠서 내뱉는 값에 뺄셈이 들어가면 안된다... 절대아니된다...
static long[] dp;
static long[] CASE=new int[10];
static long[] copied_CASE=new int[10];
static long MOD = 1_000_000_000;
static void CASE_UPDATE(){
copied_CASE = CASE.clone();
CASE[0] = copied_CASE[1];
CASE[9] = copied_CASE[8];
for(int i=1;i<=8;i++){
CASE[i] = (copied_CASE[i-1]+copied_CASE[i+1]) % MOD;
}
}
static void find(int n){
for(int i=2;i<=n;i++){
dp[i] = ((dp[i-1]*2) - (CASE[0]))%MOD ;
CASE_UPDATE();
}
}
/*# 1, 2, 3 더하기
1. d[n] = d[n-1] + d[n-2] + d[n-3] : n에서 1을 뺀 경우, n에서 2를 뺀 경우, n에서 3을 뺀 경우 (첫 숫자로 1,2,3 을 선택한경우!)
import java.util.*;
public class Main {
static int[] d;
//dp
public static int get(int n){
//d[n+1] = d[n]+d[n-1]+d[n-2]
if(n==0) return 0;
if(n==1) return 1;
else if(n==2) return 2;
else if(n==3) return 4;
else if(d[n]!=0) return d[n];
return d[n]=get(n-1)+get(n-2)+get(n-3);
}
//dfs
static int cnt=0;
public static void dfs(int n){
if(n==0) {
cnt++;
return;
}else if(n<0) return;
dfs(n-1);
dfs(n-2);
dfs(n-3);
}
public static void main(String[] args) {
d=new int[50];
Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
for(int i=0;i<t;i++){
int n=sc.nextInt();
System.out.println(get(n));
}
/* dfs
for(int i=0;i<t;i++){
int n=sc.nextInt();
dfs(n);
System.out.println(cnt);
cnt=0;
}
*/
}
}# 카드 구매하기 (11052번)
1. Optimal 부분합 문제
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
static int[] cards;
static int[] dp;
//N : 카드팩 갯수
//cards[i] : i개의 카드가 들어있는 카드팩의 가격
//N개를 충족하는 최대 금액
//1<=N<=1,000, 1<=cards[i]<=10,000
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
cards = new int[n+1];
dp = new int[n+1];
for(int i=1; i<=n; i++){
cards[i]=Integer.parseInt(st.nextToken());
}
for(int i=1; i<=n;i++){
for(int j=1; j<=i;j++){
dp[i] = Math.max(dp[i],dp[i-j]+cards[j]);
}
}
System.out.println(dp[n]);
}
}# 이동하기 (11048번)
1. 오른쪽, 아래쪽, 대각선 방향을 다 고려했으나, 각 원소가 다 자연수이기 때문에, 대각선으로 오는걸 고려할 필요가 없었음...
(합은 항상 거쳐서 오는게 더 크니까...)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
static int[][] maze;
static int[][] sum;
static int n;
static int m;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
maze= new int[n+1][m+1];
sum = new int[n+1][m+1];
for(int i=1;i<=n;i++){
st= new StringTokenizer(br.readLine());
for(int j=1;j<=m;j++){
maze[i][j]=Integer.parseInt(st.nextToken());
}
}
int max = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
sum[i][j] = maze[i][j]+Math.max(Math.max(sum[i-1][j],sum[i][j-1]),sum[i-1][j-1]);
if(sum[i][j]>max) max=sum[i][j];
}
}
System.out.println(max);
}
}# 피보나치 함수 (1003번)
import java.io.*;
public class Main{
static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
dp = new int[41][2];
dp[0][0]=1; dp[0][1]=0;
dp[1][0]=0; dp[1][1]=1;
for(int i=2; i<41; i++){ //40 까지
dp[i][0] = dp[i-1][0]+dp[i-2][0];
dp[i][1] = dp[i-1][1]+dp[i-2][1];
}
for(int i=0; i<t; i++){
int n = Integer.parseInt(br.readLine());
System.out.println(dp[n][0]+" "+dp[n][1]);
}
}
}# 가장 긴 감소하는 부분 수열 (11722번)
1. 최적 부분 구조에 해당한다 -> dp
2. dp[n] 의 정의를 내리는게 쉽지않았다. 최적 부분 구조에 해당하는게 return 값인데, 그러한 return 값을 위주로 dp[n]의 정의를 내려야 고생 안한다...
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class test{
static int[] arr;
static int[] dp;
public static void printArr(int i, int j, int n){
System.out.printf("# i=%d,j=%d : ",i,j);
for(int k=0; k<n; k++){
System.out.printf("%2d ",dp[k]);
}
System.out.println();
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
dp = new int[n];
arr = new int[n];
st = new StringTokenizer(br.readLine()," ");
for(int i=0;i<n;i++){
arr[i] = Integer.parseInt(st.nextToken());
}
int result =0;
for(int i=0; i<n; i++){
dp[i]=1;
for(int j=i-1; j>=0; j--){
//여태 너보다 큰거 몇개있었어? 그 전 친구보다 많구나?
if(arr[i]<arr[j] && dp[i]<=dp[j] ){
dp[i]=dp[j]+1;
}
// printArr(i, j, n);
}
result = Math.max(result, dp[i]);
}
System.out.println(result);
/*
7
30 29 31 28 6 10 5
*/
}
}# 가장 큰 증가 부분 수열 (11055번)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
static int[] arr;
static long[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
arr = new int[n];
dp = new long[n];
for(int i = 0; i < n ; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
//dp[n] : 수열의 증가 부분 수열중 합이 제일 큰 값
long result = 0;
for(int i=0; i<n; i++){
dp[i]+=arr[i];
long memo=0;
for(int j=i-1; j>=0; j--){
if(arr[i]>arr[j] && dp[j]>memo ){
memo= dp[j];
}
}
dp[i]+=memo;
result = Math.max(result,dp[i]);
}
// for(int i=0; i<n; i++){
// System.out.printf("%3d ",dp[i]);
// }
// System.out.println();
System.out.println(result);
}
}
/*
7
5 50 20 100 101 30 500
*/# 가장 긴 바이토닉 부분 수열 (11054번)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class test{
static int[] arr;
static int[] ldp;
static int[] rdp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
arr = new int[n];
ldp = new int[n];
rdp = new int[n];
for(int i = 0; i < n ; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
//dp[n] : S(n)을 기준으로 바이토닉수열일 때, 가장 길이가 큰 값... 점화식을 못찾겠는걸 ㅎ...?
//ldp[n] : 부분 증가수열이면서 길이 제일 큰 값
//rdp[n] : 부분 감소수열이면서 길이 제일 큰 값
for(int i=0; i<n; i++){
ldp[i]=1;
for(int j=i-1;j>=0;j--){
if(arr[i]>arr[j] && ldp[i]<=ldp[j]){ // 증가수열
ldp[i]=ldp[j]+1;
}
}
}
for(int i=n-1; i>=0; i--){
rdp[i]=1;
for(int j=i+1;j<n;j++){
if(arr[i]>arr[j] && rdp[i]<=rdp[j]){ // 감소수열
rdp[i]=rdp[j]+1;
}
}
}
// for(int i=0;i<n;i++){
// System.out.printf("%2d ",ldp[i]);
// }
// System.out.println();
// for(int i=0;i<n;i++){
// System.out.printf("%2d ",rdp[i]);
// }
// System.out.println();
int result = 0;
for(int i=0;i<n;i++){
result = Math.max(result, ldp[i]+rdp[i]-1);
}
System.out.println(result);
}
}
/*
10
1 5 2 1 4 3 4 5 2 1
*/# 가장 긴 증가하는 부분 수열5 (14003번)
1. n과 arr[n]의 값이 +-10억 사이이다.
2. 시간복잡도는 binarySearch (LogN) * 메인 for문(N) => NLogN 이다.
3. C++과 다르게 Java는 바이너리서치를 직접구현해야하므로, 부등호와 리턴인덱스에 주의하자.
4. LIS 알고리즘의 원리가 기억안난다면, 꼭 검색해서 다시 익혀두자. (geeksforgeeks 추천)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
static long[] arr;
static long[][] dict;
static long[] lis;
static int binarySearch(int start, int end, long target){
while(start<end){
int mid = (start+end)/2;
if(lis[mid] < target){
start = mid+1;
}else{
end=mid;
}
}
return end;
}
static void printArr(long[] arr, int n){
for(int i=0;i<n;i++){
System.out.printf("%2d ",arr[i]);
}
System.out.println();
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
arr = new long[n];
dict = new long[n][2];
lis = new long[n];
for(int i = 0; i < n ; i++){
arr[i] = Long.parseLong(st.nextToken());
}
//dp[n] : 수열의 증가 부분 수열중 합이 제일 큰 값
int top=0; int len = top+1;
lis[0] = arr[0];
int dictIdx=0;
dict[dictIdx][0] = len;//len
dict[dictIdx++][1] = lis[top]; //value
for(int i=1;i<n;i++){
if(lis[top] < arr[i]){
lis[++top] = arr[i];
len=top+1;
dict[dictIdx][0] = len;
dict[dictIdx++][1] = lis[top];
}
else{
int idx = binarySearch(0, top ,arr[i]);
lis[idx]=arr[i];
dict[dictIdx][0]=idx+1;
dict[dictIdx++][1]=lis[idx];
}
// printArr(lis, n);
}
System.out.println(top+1);
len = top+1;
long[] stack = new long[len];
int cnt=0;
for(int i=dictIdx-1;i>=0;i--){
// if(len==0) break;
if(dict[i][0] == len){
stack[cnt++]=dict[i][1];
len--;
}
}
len =top+1;
// for(int i=0; i<len; i++){
// System.out.println(stack[i]);
// }
for(int i=len-1;i>=0;i--){
System.out.print(stack[i]+" ");
}
}
}
/*
7
5 50 20 100 101 30 500
11
50 29 30 31 14 24 32 33 34 25 29
8
1 6 5 7 8 1 2 3
*/# 설탕배달 (2839번)
1. 이걸 어떻게 dp로 풀지..? 😢
2. 구글링해서 dp 풀이법을 찾았다..! 이해는 되는데, 어떻게 저게 직관적으로 떠오르는 걸까... 🧐
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int kg = Integer.parseInt(br.readLine());
//5kg, 3kg
int _5kg = kg/5;
int res = kg-_5kg*5;
//gready
while(true){
if(res%3==0 || _5kg==0) break;
_5kg-=1;
res=kg-_5kg*5;
}
if(res%3!=0) System.out.println(-1);
else{
int _3kg = res/3;
// System.out.println(_5kg+" "+_3kg);
System.out.println(_3kg+_5kg);
}
}
}
// DP 풀이법
// https://jhhj424.tistory.com/40
/*
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if(n<5) {
if(n==3) System.out.println(1);
else System.out.println(-1);
return;
}
int dp[] = new int[n+1];
Arrays.fill(dp, 9999);
dp[3] = 1;
dp[5] = 1;
for(int i=6; i<dp.length; i++) {
dp[i] = Math.min(dp[i-3]+1, dp[i-5]+1);
}
if(dp[n] > 9999) {
System.out.println(-1);
}else {
System.out.println(dp[n]);
}
}
}
*/# 정수 삼각형 (1932번)
1. triArr 안쓰고 dp 배열만으로도 답을 구할 수 있다. (n^2 의 공간복잡도는 아깝긴하다.)
2. 1차원배열로 dp 배열이나 triArr 배열을 선언한다면 공간복잡도는 n이 된다. (offset, strides가 귀찮다) (시간되면 해볼 것)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int triArr[][] = new int[n][n];
int dp[][] = new int[n][n];
int result=0;
for(int i=0; i<n; i++){
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<i+1;j++){
triArr[i][j]= Integer.parseInt(st.nextToken());
if(i>0){
if(j==0) {
dp[i][j]=dp[i-1][j]+triArr[i][j];
continue;
}
dp[i][j]=Math.max(dp[i-1][j-1],dp[i-1][j])+triArr[i][j];
}else{
dp[i][j] = triArr[i][j];
}
result=Math.max(result, dp[i][j]);
}
}
System.out.println(result);
// for(int i=0; i<n; i++){
// for(int j=0; j<n; j++){
// System.out.printf("%2d ", triArr[i][j]);
// }
// System.out.println();
// }
// System.out.println("# dp");
// for(int i=0; i<n; i++){
// for(int j=0; j<n; j++){
// System.out.printf("%2d ", dp[i][j]);
// }
// System.out.println();
// }
}
}# 01타일 (1904번)
1. 진짜진짜진짜진짜 점화식 찾는게 세상에서 가장 어렵따... 🤯
2. 곱셈은 언제나 오버플로우의 단골손님이지... 덧셈도 터지는데 말이야.. -> 점화식 잘못찾았다는 소리
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
//ans = ans % 15746
int mod = 15746;
//size 2(bianry 0), 1(binary 1)
//n==2 / 00 11
//n==3 / 001 100 111
//n==4 / f(3) 1001 1100 1111 / f(2) 0000 0011
//n==5 / f(5) = (f(4)-1)*2 (00들어간거 앞뒤로 1붙일때)
// +1 (1로만 이뤄진거 1붙일때)
// = 2f(4) -1 = 2f(3)+2f(2) -1
// 아근데... 곱셈... 들어가면.......... 숫자커지면 오버플로우생기는데 ㅠㅠㅠㅠ
// f(1) = 1, f(2) = 2, f(3) =3, f(4)=5
// f(5) = 8
// f(6) = 13
// 헤헷,, 점화식을 잘못찾았구만
long dp[]= new long[n+1];
//least exception handling
if(n==1) {
System.out.println(1);
return;
}
dp[1]=1; dp[2]=2;
for(int i=3; i<=n; i++){
dp[i]= (dp[i-2]+dp[i-1])%mod;
}
System.out.println(dp[n]);
}
}
728x90