[백준] 11055 - 가장 큰 증가하는 부분 수열(JAVA)

1. 소요시간 : 39분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 2
4. 문제 유형 : 다이나믹 프로그래밍
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/11055
8. 푼 날짜 : 2023.03.19

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍을 사용했다.

2. 사고과정

애초에 DP 카테고리를 고르고 와서 DP 문제라는 건 알았다. 그리고 n이 1000까지니까 이 문제는 O(n^2) 의 알고리즘으로 해결하려고 했다. 그렇게 되면 1,000,000 이 나오니 0.01초에 해당하여 시간복잡도는 널널할 것으로 생각했다. 하지만 점화식을 유도해내는 데에서 많은 시간을 소모했다.

결국 39분의 시간만에 문제를 해결했다.

3. 풀이과정

1. 우선 이전에 탐색했던 dp[i] 의 값이 있나 확인한다. 그 값과 arr[i]를 비교해서, 더 큰 값을 dp[i]로 잡는다.
2. 이제 i가 1이라면 j는 2부터 끝까지 탐색을 시작한다. arr[j] 가 arr[i] 보다 크다면, 그 이전의 값인 dp[j] 와 dp[i]+arr[j]를 비교해서 더 큰 값을 dp[j] 로 한다.
3. 마지막으로 dp[1]~ dp[n] 중 가장 큰 값이 최종 값이다.

4. 소스코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n=Integer.parseInt(br.readLine());
		int dp[]=new int[n+1];
		int arr[]=new int[n+1];
		st=new StringTokenizer(br.readLine());
		
		for(int i=1;i<arr.length;i++)
			arr[i]=Integer.parseInt(st.nextToken());
		
		
		for(int i=1;i<dp.length;i++) {
			dp[i]=Math.max(dp[i],arr[i]);
			for(int j=i+1;j<dp.length;j++) {
				if(arr[j]>arr[i]) 
					dp[j]=Math.max(dp[i]+arr[j],dp[j]);
			}
		}
		
		int max=0;
		for(int i=1;i<dp.length;i++) {
			max=Math.max(dp[i],max);
		}
		System.out.println(max);
		
		
	}
}

5. 결과

6. 회고

역시 dp 유형이 약해서 시간이 오래걸렸다.
시간이 오래 걸리더라도 혼자 점화식을 유도해 보도록 하자.
섣불리 답지에 먼저 접근하려고 하지 말자.

그리고 우선 예제의 테스트케이스라도 완벽하게 통과해내는 숏코딩 등 검증을 마치고 진짜 코딩을 시작하자. 무작정 코딩을 하고 시작했어서 중간중간 아예 다른 길로 샜었다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212