[DP 연습] BOJ_11053 가장 긴 증가하는 부분 수열 (S2)

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

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

 

첫번째는 내코드, 두번째는 구글링한 맞은 코드!

 

문제를 풀고 나서 내가 어떤 오류가 있는지 전혀 깨닫지 못하고 분한 마음으로(?) 구글링을 해보고서, 아니 왜 이렇게 어렵게 풀었는가 고민하다가 이내 나의 짧은 이해력을 반성하고 부끄러운 마음을 가지게 되었다(?)! 일단 DP문제라는 것을 염두에 두면서 메모이제이션을 계속 활용하려고 노력하는데 그게 잘 안되는데, 솔루션을 보면서 매번 무릎만 치다가 무릎이 닳아지게 생겼다..

 

우선 배열에 뭔갈 저장할 때, 단순하게 1,2차원 배열을 탐색하는 문제랑은 다르게 생각해야 할 것 같다는 생각이 들었다. 이걸 단순히 인덱스와 해당 인덱스에 해당하는 값을 가져온다, 저장한다 느낌보다는, 소위 Flat한 생각을 가지고, 첫번째 시행에서는 이런 일이 일어나겠지, 두번째 시행에서는 이런 일이 일어나겠지, 그럼 다음 시행에는 어떻게 점화식으로 표현할 수 있지? 어떻게 일반화할 수 있지? 이런 생각을 가져야 할 것 같다. (말은 쉽지!) 우선 비슷한 문제를 풀어보면서 이해력을 점검해 보아야 할 것 같다.. ㅠㅠ

 

package algo0921;

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

// 가장 긴 증가하는 부분 수열
public class BOJ_11053 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = Integer.parseInt(br.readLine());
		int[] nums = new int[N];
		int[] memo = new int[N];
		
		// 입력
		st = new StringTokenizer(br.readLine(), " ");
		for (int n = 0; n < N; n++) {
			nums[n] = Integer.parseInt(st.nextToken());
		}
		System.out.println(Arrays.toString(nums));
		
		memo[0] = 1;

		// 점화식
		for (int n = 1; n < N; n++) {
			if (nums[n] > nums[n-1]) {
				memo[n] = memo[n-1] + 1;
			} else memo[n] = memo[n-1];
		}
		System.out.println(Arrays.toString(memo));
		
		// 출력
		System.out.println(memo[N-1]);
		
	}
}

 

package algo0921;

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

// 가장 긴 증가하는 부분 수열
public class BOJ_11053_sol {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = Integer.parseInt(br.readLine());
		int[] nums = new int[N]; // 입력받은 수열을 저장할 배열
		int[] memo = new int[N]; // 메모이제이션 할 배열
		
		// 입력
		st = new StringTokenizer(br.readLine(), " ");
		for (int n = 0; n < N; n++) {
			nums[n] = Integer.parseInt(st.nextToken());
		}
		System.out.println(Arrays.toString(nums));
		
		memo[0] = 1; // 무조건 수열의 첫항은 길이가 1이니까 1로 초기화
		int ans = 1; // 이거 뭐하는 놈이냐...
		
		// 점화식
		for (int n = 1; n < N; n++) { // memo[n]을 메모이제이션 해주기 위한 첫번째 반복문
			memo[n] = 1; // 일단 memo[n] 1로 초기화
			for (int m = 0; m < n; m++) { // memo[n]을 기준으로 배열의 이전항들을 탐색할 두번째 반복문
				if (nums[n] > nums[m] && memo[n] <= memo[m]) {
					// nums[] 요소 비교 : nums[n]전항이 nums[n]보다 작은지 살펴보기 위함 
					// memo[] 요소 비교 : memo[n]은 0으로 초기화 된 상태, memo[n]전항이 memo[n]보다 큰지 살펴보기 위함
					memo[n] = memo[m] + 1;
				}
			}
			// 반복문을 돌면서 최대길이에 해당하는 값을 갱신
			ans = Math.max(ans, memo[n]);
		}
		System.out.println(Arrays.toString(memo));
		
		// 출력
		System.out.println(ans);
		
	}
}

/*
6
10 20 10 30 20 50
[10, 20, 10, 30, 20, 50]
[1, 2, 1, 3, 2, 4]
4
*/

/* 
6
10 20 10 30 20 50
[10, 20, 10, 30, 20, 50]
[1, 2, 2, 3, 3, 4]
4
*/