Yong's Tech Story

문제 풀이 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// 동전 교환(냅색 알고리즘)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int[] arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int[] dy = new int[M + 1];

		Arrays.fill(dy, Integer.MAX_VALUE); // 최소를 구할시 Dynamic 배열 최대값으로 초기화
		dy[0] = 0; // 첫번째 값은 0 (최소값)
		for (int i = 0; i < N; i++) {
			for (int j = arr[i]; j <= M; j++) {
				dy[j] = Math.min(dy[j], dy[j - arr[i]] + 1); // (이전 최소값 + 1)이 현재 값보다 작다면 교환
			}
		}
		System.out.println(dy[M]);
	}
}

정리

1. 해당 동전 문제의 첫번째 포인트는 각 숫자마다 최소 배열을 가지는 dy 배열을 선언하는 것이다.

2. 최소 값을 가져야 하기 때문에 Arrays.fill 함수를 사용하여 dy 배열을 MAX 값으로 초기화해준다.(단, dy[0]은 비교를 위해 0으로 초기화한다.

3. 문제를 풀기 위해서는 (이전 최솟값 +1) 에서 1은 현재 동전을 추가했을때의 경우로, (이전 최솟값 +1)이 현재 값보다 작다면 최솟값을 가지는 경우의 수 이기 때문에 더 작은 값으로 교체해주어야 한다. 이 문제의 핵심 포인트이다.  

문제 풀이 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	/**
	 * 숫자가 이전 값보다 큰 경우, (현재 값)보다 (이전 값) +1이 크다면 변경
	 * 
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args) throws IOException {
		// 최대 부분 증가 수열(LIS)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int[] arr = new int[N];
		int[] dy = new int[N]; // 각 숫자마다 현재 최대 수열
		int max = 0;

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			dy[i] = 1;
		}

		for (int i = 1; i < arr.length; i++) {
			for (int j = i - 1; j > 0; j--) {
				// 현재 값 기준으로 앞에 값이 현재값 보다 작다면
				if (arr[i] > arr[j]) {
					// 숫자가 이전 값보다 큰 경우, (현재 값)보다 (이전 값) +1이 크다면 변경
					dy[i] = Math.max(dy[i], dy[j] + 1);
					max = Math.max(max, dy[i]);
				}
			}
		}
		System.out.println(max);

	}

}

정리

1. 해당 문제는 랜덤한 숫자가 있을시 가장 긴 부분수열을 찾는 문제로 처음에는 투포인터나 DFS 문제인줄 알았으나 LIS 알고리즘을 사용하는 DP문제임을 알게 되었다.

2. 들어오는 숫자 배열마다 최대 부분수열을 각 배열(dy)로 저장하며, 현재 숫자를 기준으로 앞의 숫자들과 비교하여 더 작은 숫자가 있을시, 해당 숫자의 부분수열(dy[]) 값의 +1 증가한 값으로 현재 dy 배열을 저장한다.

3. 이 문제에서 중요한 부분은 현재 배열의 숫자가 이전값보다 크다면, 해당 값들만 dy 값을 비교하여 현재 배열들을 채워나가는 형식이다.

4. 주의 할 점은 마지막 배열이 작은 값이 들어와 이전 값보다 작아 비교가 안되는 경우가 있으니, 마지막 값이 가장 긴 부분수열이 되리라는 보장이 없다. 

문제 풀이 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	/**
	 * 시간내 최대점수 구할시 배열 스코어 끝에서부터 탐색해야 함!!!
	 * 
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args) throws IOException {
		// 최대점수 구하기(냅색 알고리즘)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken()); // 문제의 개수
		int M = Integer.parseInt(st.nextToken()); // 제한 시간

		int[] maxScore = new int[M + 1];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int score = Integer.parseInt(st.nextToken());
			int time = Integer.parseInt(st.nextToken());

			// !! 중요사항 - 배열 끝부터 탐색 !!
			for (int j = M; j >= time; j--) {
				// 현재 MAX 스코어보다 이전 시간의 스코어가 높다면
				maxScore[j] = Math.max(maxScore[j], maxScore[j - time] + score);
			}
		}
		System.out.println(maxScore[M]);
	}
}

정리

1. 동적 프로그래밍 문제는 기본적으로 최댓값,최솟값등을 구하기 위하여 배열을 재사용한다는 것을 인지한다.

2. 문제의 핵심 중 하나는 시간내에 가장 높은 점수를 구하기 위해 앞에서 탐색하는 Bottom-UP 방식이 아닌 배열 끝에서부터 탐색하는 Top-Down 방식을 사용해야 한다.

3. 현재 시간별 최대스코어 배열(maxScore)에 값이 존재하는 경우  (현재 최대스코어 < (현재시간-감소시간)의 최대스코어 + (감소시간의 점수) ) 일경우 더 높은 값으로 대체한다.

4. 결론적으로 배열 끝부터 시간마다 모든 점수를 입력하여 그 시점에 더한 값이 더 높은 값이 있다면 변경해준다.