[백준 알고리즘 자바] 11722: 가장 긴 감소하는 부분 수열

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

11722번: 가장 긴 감소하는 부분 수열

---

문제

• 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.
• 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
• 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

• 첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

입출력 예제

---

풀이방식설계

1. 각 길이를 담을 배열을 이용해서 수열 위치에 대한 각 길이를 구한다.

2. 가장 큰 길이(값)을 출력한다.

---

풀이과정(BufferedReader)

1. 수열을 담을 배열과 각 길이를 담을 배열을 선언한다.

• seq() : 입력받은 수열의 값들을 저장한다.
• dp() : 각 길이를 담는다.

2. seq() 배열에 입력받은 값을 담는다.

• BufferedReader 등에 대한 자세한 설명은 아래 링크를 참조 부탁드립니다.
• '기초이론/JAVA' 

'기초이론/JAVA' 카테고리의 글 목록

3. 결과 개수를 담을 변수 cnt를 선언하고 0으로 초기화한다.

 

4. 2중 for문을 사용하되, 위의 for문 안에 dp[i] = 1 코드를 추가한다.

• 수열의 길이는 무조건 1부터 시작하기 때문이다.

5. seq 배열에서 앞 인덱스의 값이 더 크다면 dp[i] 와 dp[j] + 1 을 비교해서 더 큰 값을 dp[i] 에 넣는다.

• dp[i] 는 위의 for문에서 작성된 코드로 인해 1이라는 값이 무조건 들어간다.
• dp[j] 는 이전에 들어간 dp[i] 값을 의미한다. 즉, 이 값에 1을 더해서 길이를 1 더해주는 것이다.
• Math.max(a, b) : a 와 b를 비교하여 더 큰 값을 변수에 저장한다.

5. cnt 변수와 dp[i] 를 비교하여 더 큰 값을 cnt에 저장하고 출력한다.

---

답안소스

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 size = Integer.parseInt(br.readLine());
		
		int[] seq = new int[size];
		int[] dp = new int[size];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<size; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
		
		int cnt = 0;
		for(int i = 0; i < size; i++) {
			dp[i] = 1;
			
			for(int j = 0; j < i; j++) {
				
				if(seq[j] > seq[i]) {
					dp[i] = Math.max(dp[i], dp[j]+1);
					
				}
				
			}
			cnt = Math.max(cnt, dp[i]);
		}
		System.out.println(cnt);
	}
}