글 읽기 - [c++/DP]O(N^2)코드중 틀린 점이 궁굼합니다

thyung 4년 전 0

LIS O(N^2)알고리즘 참고하여 코드를 짜봤습니다. 혹시 틀린점이 있다면 무엇인지 알고 싶습니다. 그리고 혹시 이 문제가 N^2으로 풀면 시간초과나는지 궁굼합니다. 게시판에 있는 반례 3개 대입해 봤는데 정답은 나왔습니다. 생각하지 못한 점이 있는 거 같아서 질문드렸습니다. 감사합니다.

#include <iostream>
#include <stack>
using namespace std;
int arr[1001];
int dp[1001];
stack<int> st;
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	int max = 0;
	for (int i = 1; i <= n; i++) {
        dp[i]=1;
		for (int j = 1; j < i; j++) {
			if (arr[i] > arr[j] && dp[j]+1>dp[i]) {
				dp[i] = dp[j] + 1;
				if (max < dp[i]) max = dp[i];
			}
		}
	}
	for (int i = n; i > 0; i--) {
		if (max == 0) break;
		if (dp[i] == max) {
			st.push( arr[i]);
			max--;
		}
	}
	int stsize = st.size();
	cout << stsize << '\n';
	for (int i = 0; i < stsize; i++) {
		cout << st.top() << ' ';
		st.pop();
	}
	return 0;
}

djm03178 4년 전 0

https://ideone.com/aRbRwE

thyung 4년 전 0

감사합니다. 한 자리 수열의 경우 max에 값이 들어가지 않아서 틀리는 거였네요. max가 0일때 1로 변경하는 코드 추가하니 맞았습니다. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[c++/DP]O(N^2)코드중 틀린 점이 궁굼합니다

thyung 4년 전 0

djm03178 4년 전 0

thyung 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말