❓ 가장 긴 증가하는 부분 수열
🏷️ 관련 주제 : Dynamic Programming
💦 나의 시도
어제도 다이나믹 프로그래밍 문제가 나와서 알고리즘 정리할 때, LIS(Longest Increasing Subsequence)를 봤었는데
풀이 방법이 정확히 생각나지 않아 LCS(Longest Common Subsequence) 문제 풀이 코드 따라 쓰면서 사용했던 방법을 생각하며 문제를 풀어보았습니다.
제일 앞 숫자부터 차례대로 뒷 숫자 탐색, 큰 값이 나오면 개수 및 마지막 숫자 업데이트
- int
N선언 : 입력할 숫자 개수 - int[]
A선언 : 입력한 숫자를 차례대로 담을 길이N인 배열 - int[]
lastElement선언 :i번째 인덱스에A[i]에서 시작한 수열의 마지막 원소를 담을 길이N인 int 배열 - int[]
cnt선언 :i번째 인덱스에A[i]에서 시작한 수열의 길이를 담을 길이N인 int 배열 - int
maxLen을 0으로 초기화 : 길이가 제일 긴 수열의 길이 - 0 ~ (N - 1) 범위를 반복문을 돌기
- 반복문의 인덱스 int
i에 대하여i번째 입력값을 받아A[i]에 할당 - 0 ~ i 범위를 반복문을 돌면서 반복문의 인덱스
j에 대하여A[i]가 lastElement[j]` 이상이면 다음을 실행lastElement[j]에A[i]할당cnt[j]++maxLen에maxLen과cnt[j]중 더 큰 값 할당
- 반복문의 인덱스 int
maxLen출력하기
❌ 틀렸습니다.
수열이 단조 증가 수열이어도 되는 줄 알고 두 수를 비교하였을 때, 그 값이 같은 경우도 수열에 추가하였는데
단조 증가가 아닌 증가 함수의 최대 길이를 원하는 것인 것이었습니다.
그래서 2중 for문에서 안쪽 for문 안의 조건문을 수정하였습니다.
// 이전 코드
if (A[i] >= lastElement[j]) {...}
// 수정한 코드
if (A[i] > lastElement[j]) {참고) 수열 ${a_1, a_2, a_3, ...}$에 대하여
- 단조 증가 수열 : $\forall a_i,\ a_j \in {a_n}_{n\in \mathbb{N}},\quad i < j \ \Rightarrow \ a_i \leq a_j$
(수열의 임의의 두 원소에 대하여 뒷 숫자가 앞 숫자보다 크거나 같다.) - 증가 수열 : $\forall a_i,\ a_j \in {a_n}_{n\in \mathbb{N}},\quad i < j \ \Rightarrow \ a_i \lt a_j$
(수열의 임의의 두 원소에 대하여 뒷 숫자가 앞 숫자보다 크다.)
❌ 틀렸습니다.
두 수를 비교했을 때, 뒤에 오는 숫자가 더 크면 무조건 수열에 추가하는 코드를 작성하였습니다.
하지만 문제에서 요구하는 것은 가장 긴 수열이기 때문에 무조건 추가하지 않고 더 긴 수열을 만드는 방법이 존재할 수도 있습니다.
예시 입력
4
1 10 2 3예시 출력
3제가 쓴 코드에서 각 숫자로 시작해서 만들수 있는 가장 긴 수열은 다음과 같습니다.
{1, 10}, {10}, {2, 3}, {3}그러므로 2를 출력하게 됩니다.
하지만 1 뒤에 10이 아닌 2, 3을 추가하게 되면 {1, 2, 3}이라는 수열을 만들 수 있습니다.
따라서 정답은 3이 됩니다.
❌ 틀렸습니다.
어제 보았던 다이나믹 프로그래밍 방식은 뒤의 원소부터 탐색을 해 왔던 것 같아서 코드를 수정해 보았습니다.
cnt[N - 1] = 1;
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for (int i = N - 2; i >= 0; i--) {
for (int j = N - 1; j >= i + 1; j--) {
if (A[i] < A[j] && cnt[j] + 1 > cnt[i]) {
cnt[i] = cnt[j] + 1;
}
}
}lastElement삭제- 맨 뒤의 숫자로 시작하는 수열은 자기자신 밖에 없으므로
cnt[N - 1]에 1을 할당
- 입력값 받아서
A에 할당하기 - 가장 긴 수열 길이 구하기
- 숫자를 뒤에서부터 탐색
- (N - 2) ~ 0 범위를 반복문을 돌면서 그 뒤의 숫자 탐색
- 반복문 (N - 1) ~ (i + 1) 범위 반복문 돌기
- 뒷 숫자
A[j]가 앞 숫자A[i]보다 크고A[j]로 시작하는 수열의 길이가 이전에 이어붙인 수열의 길이보다 더 길면(cnt[j] + 1 > cnt[i]),A[i]에A[j]로 시작하는 수열 이어 붙이기 - 수열 길이
cnt[i]에cnt[j] + 1할당
- 숫자를 뒤에서부터 탐색
현재 숫자에 대하여 뒤에 오는 숫자로 시작하는 수열 중, 가장 긴 수열을 이어주어야 합니다.
뒤에 오는 j번 인덱스 숫자로 시작하는 수열의 길이는 cnt[j]입니다.
이 수열 cnt[j]에 i번 인덱스 숫자를 앞에 붙이는 것이므로 수열의 길이 cnt[i]는 cnt[j] + 1이 됩니다.
따라서 증가 수열 조건을 만족하고(A[i] < A[j]) 뒤에오는 수열의 길이가 현재 붙인 수열의 길이보다 더 길 때(cnt[j] + 1 > cnt[i]), cnt[i]에 cnt[j] + 1을 할당하였습니다.
3. 결과값 출력하기 (cnt[0])
❌ 틀렸습니다.
A[0]로 시작하는 수열의 길이가 가장 길 줄 알았는데
생각해 보니 아닌 것 같아서
int maxLen을 다시 살려 가장 긴 길이 구함.
- 앞 숫자의 뒤에 더 큰 숫자가 없을 때는 1을 할당해야하므로
cnt의 모든 인덱스에1을 할당 (Arrays.fill(cnt, 1);) - int
maxLen을0으로 초기화 - 이중 for문의 안쪽 for문이 끝난 뒤에
maxLen에maxLen과cnt[i]중 더 큰 값을 할당 - 결과값으로
maxLen을 출력
❌ 틀렸습니다.
N과 $A_i$의 범위를 체크
$1 \leq N \leq 1,000$
$1 \leq A_i \leq 1,000$
N이 1인 테스트 케이스를 생각해 보았습니다.
입력 예시
1
1위의 경우 만들 수 있는 수열은 {1}이 유일하므로 정답은 1
하지만 제가 앞에서 쓴 코드는 0을 출력하고 있었습니다.
왜 그럴까? 생각해 본 결과 N이 1인 경우 이중 for문을 돌지 않고 maxLen을 그대로 출력하기 때문이었습니다.
따라서 위의 경우 1을 출력하기 위해 maxLen을 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());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] A = new int[N];
int[] cnt = new int[N];
Arrays.fill(cnt, 1);
int maxLen = 1;
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for (int i = N - 2; i >= 0; i--) {
for (int j = N - 1; j >= i + 1; j--) {
if (A[i] < A[j] && cnt[j] + 1 > cnt[i]) {
cnt[i] = cnt[j] + 1;
}
}
maxLen = Math.max(maxLen, cnt[i]);
}
System.out.println(maxLen);
}
}
