728x90
반응형
* 공부 목표
DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052
문) 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입) 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
풀이
1. 테이블 정의
- 입력 값 A만큼 반복 입력받고, Ai에 해당하는 배열을 저장하여 최대값 부분 수열 구하기
2. 점화식 : D[i] = D[j] +1;
3. 초기값 : D[i] = 1;
(예시) D[]에 들어가는 수열의 길이
| arr | 10 | 20 | 10 | 30 | 20 | 50 |
| D | 1 | 2 | 1 | 3 | 1 | 4 |
즉, D[i]는 최소 1이상의 길이를 가지며,
현재값이 이전값보다 클 때 +1씩 누적시키면 됨.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
int[] d = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i=0; i<n; i++) {
if(st.hasMoreTokens()) {
arr[i] = Integer.parseInt(st.nextToken());
}
}
for(int i=0; i<n; i++) {
d[i] = 1; //자기 하나면 값이 1.
for(int j=0; j<i; j++) {
//이전의 원소가 현재값보다 작고, 현재 누적값(1)보다 이전 누적값+1이 더 클때
if(arr[j] <arr[i] && d[i] < d[j] +1) {
d[i] = d[j] +1;
}
}
}
int max = 0;
for(int i=0; i<n; i++) {
max = d[i] > max ? d[i]:max;
}
br.close();
System.out.println(max);
}
}
맨 처음에는 포도주 시식 문제처럼 oxo, oox, xoo ... 경우의 수를 따져가며 구하려고 했음.
그런데 도저히 답이 안 나와서 고민했을 때,
이전과 현재 값 비교하며 1씩 누적시키면 된다는 부분을 캐치함.
낭패였던 점은, 최댓값 구하는 for문 안에서 dp도 함께 돌리려고 했던 것
그리고 중첩 for문을 생각하지 못했던 것.
순간 여러가지 사고가 섞여서 분별이 안 됐던 것 같다. ㅜㅜ
'알고리즘' 카테고리의 다른 글
| [백준] 스택 - 9012번 괄호 | 1개만 입력 받기, stack 처리 (1) | 2023.10.06 |
|---|---|
| [백준] DP - 11055번, 가장 큰 증가하는 부분 수열 (1) | 2023.10.05 |
| [백준] DP - 2156번, 포도주 시식 (다른 풀이 봄) (0) | 2023.10.03 |
| [백준] 스택 - 28278번, 스택2 (0) | 2023.10.01 |
| [백준] DP - 9465번, 스티커 (다른 풀이 봄) (1) | 2023.10.01 |