[백준 알고리즘 자바] 11054: 가장 긴 바이토닉 부분 수열

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

11054번: 가장 긴 바이토닉 부분 수열

---

문제

• 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.
• 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.
• 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

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

출력

• 첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

입출력 예제

---

풀이방식설계

1. i 번째 배열의 값을 기준으로 해서 왼쪽, 오른쪽에 대한 길이를 담을 배열들을 이용해서 수열 위치에 대한 각 길이를 구한다.

2. 길이를 구한 두 배열을 더한 후에 -1을 해서 중복값을 빼준다.

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

 

아래 글을 참조하면 이해하기 더 수월할 것이다.

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

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

---

풀이과정(BufferedReader)

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

• seq() : 입력받은 수열의 값들을 저장한다.
• dpL(), dpR() : 각각 왼쪽, 오른쪽 길이 값들을 저장한다.

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

• BufferedReader 등에 대한 자세한 설명은 아래 링크를 참조하여 더 자세히 알아볼 수 있다.
• '기초이론/JAVA' 

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

3. 왼쪽과 오른쪽 수열의 길이를 구할 메소드를 각각 선언한다.

• LPD(), RPD() : 순서대로 왼쪽, 오른쪽 길이를 구할 메소드이다.

4. LPD() 메소드에는 i가 0부터 수열의 길이만큼 1씩 증가하는 for문을 작성한다.

• 수열의 길이는 무조건 1부터 시작하기에 dpL[ i ] = 1 코드를 추가한다.
• 앞(왼쪽) 부터 차례로 인덱스가 하나씩 증가하는 for 문이다.

5. seq[ i ] 번째 값이 seq[ j ] 번째 값보다 크다면 dpL[ i ] 에는 dpL[ i ]와 dpL[ j ] +1 중에 더 큰 값을 넣는다.

• Math.max(a, b) : a 와 b를 비교하여 더 큰 값을 변수에 저장한다.
• 기준값인 seq[ i ] 번째 값이 그보다 앞에 위치한 seq[ j ] 보다 크다면 이는 수열이 맞다.
• dpL[ i ] 번째 값과 dpL[ j ] +1 값을 비교해서 더 큰 값을 dpL[ i ]에 넣는다.
• dpL[ j ] +1 은 dpL[ i ] 배열의 값에서 길이가 1 늘어난 것으로, 조건이 일치해서 길이가 증가된 것을 의미한다.

6. RPD() 메소드에는 i가 수열의 길이-1 부터 0까지 1씩 감소하는 for문을 작성한다.

• 위와 마찬가지의 이유로 dpR[ i ] = 1 코드를 추가한다.
• 뒤(오른쪽) 부터 차례로 인덱스가 하나씩 감소하는 for 문이다.

7. 5번과 동일한 방식으로 코드를 수정 및 작성한다.

 

8. 두 메소드가 다 작성되었으면 메인으로 넘어와서 결과 개수를 담을 변수 cnt를 선언한다.

 

9. cnt 변수와 dpL[ i ] + dpR[ i ] 를 비교하여 더 큰 값을 cnt에 저장한다.

• Math.max(a, b) : a 와 b를 비교하여 더 큰 값을 변수에 저장한다.
  

10. cnt에 -1 을 해주고, 그 값을 출력한다.

• dpL[ i ] 배열과  dpR[ i ] 배열을 그대로 합쳤기에 중복값이 존재한다. 이를 없애주기 위해 cnt에 -1을 해준다.
• 혼자서 풀었을 때는 왜 8이 나오는지 이해하지 못했다. 그래서 아래 링크를 참고하여 이해하고, 코드를 재수정했다.

https://st-lab.tistory.com/136

[백준] 11054번 : 가장 긴 바이토닉 부분 수열 - JAVA [자바]

 

 

---

답안소스

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

public class Main {
	static int size;
	static int[] seq;
	static int[] dpL, dpR;
	
	public static void LDP() {
		for(int i=0; i<size; i++) {
			dpL[i] = 1;
			
			for(int j=0; j<i; j++) {
				if(seq[i] > seq[j]) {
					dpL[i] = Math.max(dpL[i], dpL[j]+1);
				}
			}
		}
	}
	
	public static void RDP() {
		for(int i=size-1; i>=0; i--) {
			dpR[i] = 1;
			
			for(int j=size-1; j>i; j--) {
				if(seq[i] > seq[j]) {
					dpR[i] = Math.max(dpR[i], dpR[j]+1);
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		size = Integer.parseInt(br.readLine());
		seq = new int[size];
		dpL = new int[size];
		dpR = new int[size];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<size; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
		
		LDP();
		RDP();
		
		int cnt = 0;
		for(int i=0; i<size; i++) {
			cnt = Math.max(cnt, dpL[i]+dpR[i]);
		}
		System.out.println(cnt -1);
	}
}