이 문제는 말 그대로 가장 긴 감소하는 부분 수열의 길이를 구하면 된당😝
입력으로 들어오는 수열의 크기를 먼저 입력받고 수열이 들어온다. 반복문으로 받으면 된당
아래는 전체 소스코드다🙄
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class boj11722 {
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int num = Integer.parseInt(br.readLine());
int[] seq = new int[num]; // 수열 입력받을 배열
int[] dp = new int[num]; // dp 배열 - 각 요소까지의 최장 감소수열 길이
Arrays.fill(dp, 1);
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
br.close();
for(int i = 0; i < num; i++) {
seq[i] = Integer.parseInt(st.nextToken());
}
// dp 계산
for(int i = 0; i < seq.length; i++) {
int idx = -1;
int maxLength = -1;
for(int j = 0; j < i; j++) {
if(seq[i] < seq[j] && maxLength < dp[j]) {
maxLength = dp[j]; // maxLength 갱신
idx = j;
}
if(idx != -1)
dp[i] = dp[idx] + 1;
}
}
// dp 배열의 최댓값 출력
int solution = Arrays.stream(dp).max().getAsInt();
bw.write(Integer.toString(solution));
bw.flush();
bw.close();
} catch (Exception e) {
e.printStackTrace();
}
}
}
여기서 dp계산은 아래의 반복문에서 이뤄진다🤭
수열의 원소 별로, 차례로 값을 계산한다🤗
dp[i]
👉🏻 부분 수열 seq(0,i)
내의 가장 긴 감소하는 수열의 길이.
for(int i = 0; i < seq.length; i++) {
int idx = -1;
// maxLength는 검사하는 원소 이전의 가장 긴 감소하는 수열의 길이임
int maxLength = -1;
for(int j = 0; j < i; j++) {
// 감소하는 수열: seq[i]가 seq[j]보다 작아야함.
// 그리고 maxLength가 가장 긴 인덱스를 idx에 저장한다.
if(seq[i] < seq[j] && maxLength < dp[j]) {
maxLength = dp[j]; // maxLength 갱신
idx = j;
}
// idx가 -1이 아니면 (= 최장 비내림차순 수열 길이가 바뀌었으면)
if(idx != -1)
dp[i] = dp[idx] + 1;
}
}
내가 실수 했던 부분이 있는데, maxLength
를 반복문 내에서 1로 초기화했던 것이다. 내가 dp를 전부 1로 초기화해서, 원소별로 maxLength와 비교했을 때 갱신이 이뤄지지 않았고, idx가 그대로 -1이어서 dp[i] = dp[idx] + 1;
이 실행되지 않았다.
사소한 실수였는데 꽤나 기억에 남을 거 같다. 하하
2020.03.30 수정
내가 왜 저렇게 풀었는지 모르겠다.
일단 자바로 쓴 코드에서 잘못한 부분이 있었다.
for(int j = 0; j < i; j++) {
if(seq[i] < seq[j] && maxLength < dp[j]) {
maxLength = dp[j]; // maxLength 갱신
idx = j;
}
if(idx != -1)
dp[i] = dp[idx] + 1;
}
대체 왜 dp[i]를 for j 안에서 계속 갱신한거냐구..ㅎ
그래서 파이썬 코드에서는 j 반복 끝내고 나서 갱신해주었다.
N = int(input())
A = list(map(int, input().split()))
dp = [1]*N
for i in range(1, N):
idx = -1
maxLength = -1
for j in range(i):
if A[j] > A[i] and dp[j] > maxLength:
maxLength = dp[j]
idx = j
if idx != -1:
dp[i] = dp[idx] + 1
print(max(dp))
파이썬으로 다시 풀면서 짜증났던 부분이 마지막에 max(dp)로 답을 내는 거.. 였다.
결국에는 이런식으로 ans
변수를 둬서 마지막에 최댓값을 찾을 필요는 없게 수정했다. 하지만 더 좋은 방법이 있을 것 같은데 어떤 방식을 써야 답을 dp[N-1]로 만들 수 있을지 모르겠다.
N = int(input())
A = list(map(int, input().split()))
dp = [1]*N
ans = 1
for i in range(1, N):
idx = -1
maxLength = -1
for j in range(i):
if A[j] > A[i] and dp[j] > maxLength:
maxLength = dp[j]
idx = j
if idx != -1:
dp[i] = dp[idx] + 1
ans = max(dp[i], ans)
# 이렇게 하면 dp[N-1]이 최댓값이 되지 않을 때에도
# 답을 한 번에 낼 수 있다.
print(ans)
더 찾아봐야겠다.