[알고리즘] 백준 - 다이나믹 프로그래밍 관련 문제 2

알고리즘 문제 출처 : 백준 - 11053번 : 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

내가 작성한 코드

다이나믹 프로그래밍 말고 다른 방법으로 풀어볼 수 있을 것 같아서 도전했다가 실패하고 결국 다이나믹 프로그래밍으로 풀었다. 

먼저 check에 1씩 할당해야 한다.(어느 수이든 1가지 방법 이상이기 때문) 앞에 있는 numArr[j]보다 numArr[i]가 수의 크기가 더 크고, check[j]+1보다 check[i]의 개수가 더 적은 경우, check[i]에 check[j]+1을 할당한다.

최종적으로 배열 check에서 가장 큰 수를 뽑아내면 된다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          int n = sc.nextInt();
          int[] numArr = new int[n];
          int[] check = new int[n];
          for(int i=0; i<n; i++) {
              numArr[i] = sc.nextInt();
          }
          for(int i=0; i<n; i++) {
              check[i] = 1;
              for(int j=0; j<i; j++) {
                  int temp = check[j] + 1;
                  if(numArr[j] < numArr[i] && temp > check[i]) {
                      check[i] = temp;
                  }
              }
          }
          int max = check[0];
          for(int i=1; i<n; i++) {
              if(max < check[i]) {
                  max = check[i];
              }
          }
          System.out.println(max);
    }
}

 

 

---

알고리즘 문제 출처 : 백준 - 14002번 : 가장 긴 증가하는 부분 수열 4 https://www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

 

내가 작성한 코드

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();;
    	int[] numArr = new int[n]; //입력받을 숫자들
    	int[] check = new int[n]; //해당 숫자까지 가장 긴 증가하는 부분 수열 개수
    	int[] before = new int[n]; //영향을 준 바로 직전 인덱스
    	for(int i=0; i<n; i++) {
    		numArr[i] = sc.nextInt();
    	}
    	for(int i=0; i<n; i++) {
    		check[i] = 1; //해당 숫자까지 가장 긴 증가하는 부분 수열 개수가 최소 1개 이상은 되므로 1 저장
    		before[i] = -1; //인덱스 0과 기본값 0에 혼동이 없도록 기본값으로 -1 세팅
    		for(int j=0; j<i; j++) {
    			int temp = check[j] + 1;
    			if(numArr[j] < numArr[i] && check[j] + 1 > check[i]) {
    				check[i] = temp;
    				before[i] = j;
    			}
    		}
    	}
    	int max = check[0];
    	int index = -1;
    	for(int i=1; i<n; i++) {
    		if(max < check[i]) {
    			max = check[i]; //max에 최댓값 저장
    			index = i; //index에 최댓값일 때 i 저장
    		}
    	}
    	System.out.println(max); //최댓값 출력
    	
    	if(index == -1) { //가장 긴 증가하는 수열이 없을 때
    		System.out.println(numArr[0]);
    	}
    	else { //가장 긴 증가하는 수열이 있을 때
    		String temp = "";
    		while(index>=0) {
    			temp = numArr[index]+" "+temp;
    			index = before[index];
    		}
    		System.out.println(temp);
    	}
	}
}

 

 

---

알고리즘 문제 출처 : 백준 - 1912번 : 연속합 https://www.acmicpc.net/problem/1912

1912번: 연속합

 

내가 작성한 코드

n이 100,000인데 처음 생각해낸 방법은 이중 for문이었다. 시간복잡도는 100,000의 제곱으로 걸리지만, 별다른 방도가 생각나지 않아서 일단 처음 생각한대로 풀어봤다.

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();;
    	int[] numArr = new int[n];
    	int[] sum = new int[n];
    	for(int i=0; i<n; i++) {
    		numArr[i] = sc.nextInt();
    	}
    	for(int i=0; i<n; i++) {
    		int total = 0;
    		sum[i] = numArr[i];
    		for(int j=i; j<n; j++) {
    			total += numArr[j];
    			if(sum[i]<total) {
    				sum[i] = total;
    			}
    		}
    	}
    	int max = sum[0];
    	for(int i=0; i<n; i++) {
    		if(max < sum[i]) {
    			max = sum[i];
    		}
    	}
    	System.out.println(max);
    }
}

역시나 시간 초과...

 

그래서 다이나믹 프로그래밍으로 다시 풀었다.

for문을 돌려서 배열 numArr에 현재 수를 부르고, 배열 sum에서 직전까지의 연속합을 불러서 비교한다. numArr[i]는 i번째 수이고, sum[i]는 i까지의 최대 연속합이다. 만일 직전까지의 연속합에 현재 수를 더한 것이 현재 수보다 크다면 sum[i]에 직전까지의 연속합+현재 수를 저장한다. 그렇지 않다면 sum[i]에 현재 수만 저장해서 연속합을 새롭게 시작한다.

import java.util.Scanner;

public class Main {
	
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();;
    	int[] numArr = new int[n];
    	int[] sum = new int[n];
    	for(int i=0; i<n; i++) {
    		numArr[i] = sc.nextInt();
    	}
    	sum[0] = numArr[0];
    	for(int i=1; i<n; i++) {
    		if(numArr[i]+sum[i-1] > numArr[i]) {
    			sum[i] = numArr[i]+sum[i-1];
    		}
    		else {
    			sum[i] = numArr[i];
    		}
    	}
    	int max = sum[0];
    	for(int i=1; i<n; i++) {
    		if(max < sum[i]) {
    			max = sum[i];
    		}
    	}
    	System.out.println(max);
    }
}

 

 

---

알고리즘 문제 출처 : 백준 - 1699번 : 제곱수의 합 https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

 

내가 작성한 코드

D[N]을 자연수 N을 제곱수의 합으로 나타낼 때 그 항의 최소의 개수로 정의한다. D[N]은 D(N-1)+1, D(N-4)+4, D(N-9)+9, ...로 나타낼 수 있는데 이것을 좀 더 일반화하면 D[N] = min(D[N-i^2] +1)으로 나타낼 수 있다.

import java.util.Scanner;

public class Main {
	
    public static void main(String args[]) {
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int[] check = new int[n+1];
    	int temp = 0;
    	for(int i=1; i<=n; i++) {
    		check[i] = Integer.MAX_VALUE;
    		for(int j=1; j*j<=i; j++) {
    			temp = check[i-(int)Math.pow(j, 2)] + 1;
    			if(check[i] > temp) {
    				check[i] = temp;
    			}
    		}
    	}
    	System.out.println(check[n]);
    }
}

 

 

---

알고리즘 문제 출처 : 백준 - 2225번 : 합분해 https://www.acmicpc.net/problem/2225

2225번: 합분해

 

내가 작성한 코드

0~N까지의 정수 중에서 # + # + # + ... + # = N (정수 #은 k개)가 되게 해야 하는데, 마지막에 더해주는 수를 L이라고 할 때, # + # + # + ... + L = N (정수 #은 k-1개)로 정의할 수 있다. 

이를 다시 점화식으로 세우면 정수 k개를 더해서 N이 되는 경우의 수 D[k][N]은 D[k-1][N-L]의 합으로 나타낼 수 있는데, 그러면 아래와 같은 삼중 for문이 나오게 된다.(N과 k의 입력 범위가 1~200까지라서 시간 복잡도에서 가능하다)

import java.util.Scanner;

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