11568번 민균이의 계략
이왜틀?
5년전 틀렸습니다를 받은 문제.
당시 코드를 보자.
int n=Integer.parseInt(br.readLine());
int[] arr=new int[n];
StringTokenizer st=new StringTokenizer(br.readLine()," ");
for(int i=0;i<n;i++) arr[i]=Integer.parseInt(st.nextToken());
int cm=1;
for(int i=0;i<n-1;i++) {
int cnt=1;
int bf=arr[i];
for(int j=i+1;j<n;j++) {
if(arr[j]>bf) {
cnt++;
bf=arr[j];
}
}
if(cnt>cm) cm=cnt;
}
bw.write(cm+"");
그리디로 푼 것 같다.
이걸로는 찾지 못한 예외 케이스가 있었겠지.
문제 분류가 DP니 그렇게 접근해보자.
설계
점화식을 세운다.
수열 A[0] 부터 A[N - 1] 이 있을 때 dp[i] 는 i를 마지막으로 하는 부분순열의 길이다.
A[i] 앞에 있는 원소들 중 A[j] < A[i] 인 경우만 고려한다.
그 중 가장 긴 부분수열에 A[i]를 붙인다.
기본적으로 자기 자신을 포함하니 dp[i] = 1 에서 시작
dp[i] = arr[j] < arr[i] ? max(dp[i], dp[j] + 1) : dp[i]
구현
int N=Integer.parseInt(br.readLine());
int[] arr = new int[N];
int[] dp = new int[N];
StringTokenizer st=new StringTokenizer(br.readLine()," ");
for (int i = 0 ; i < N ; i++) {
arr[i]=Integer.parseInt(st.nextToken());
}
// DP
for (int i = 0 ; i < N ; i++) {
dp[i] = 1;
for (int j = 0 ; j < i ; j++) {
dp[i] = arr[j] < arr[i] ? Math.max(dp[i], dp[j] + 1) : dp[i];
}
}
int result = 0;
for (int i = 0 ; i < N ; i++) {
// 가장 긴 부분수열
result = Math.max(result, dp[i]);
}
bw.write(String.valueOf(result));
bw.flush();
채점
반성
시간복잡도가 O(N^2) 인데 N이 작아서 상관없다.
1회 틀린 것은 삼항연산자 마지막에 1을 박아둬서 초기화되어서 발생한 문제.
항상 눈을 부릅뜨고 살펴보자.
코드 확인