글 읽기 - LIS 구하는 방법으로 해봤는데.. 틀린 케이스가 있을까요?

furyhunter 6년 전 0

문제를 보니까.. 결국에는 LIS를 구하는 문제더라구요..

그래서 LIS 구하는 방법 그대로 사용해봤는데 틀린걸로 나오네요..

혹시 틀린 케이스나 제가 놓친 부분이 있을까요?

#include <iostream>

using namespace std;

//이전 상자보다 크기가 크면 상자를 넣을 수 있음
//최대로 넣을 수 있는 상자의 수를 출력

//결국엔 LIS를 구하는 방법과 같음.
//각 숫자마다 이전 단계의 수와 dp 값보다 크면 dp 값을 증가

int main()
{
	int N;
	int table[1001] = { 0 };
	int dp[1001] = { 0 };
	int max = 0;

	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> table[i];
		dp[i] = 1;
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			if (table[i] > table[j] && dp[j] + 1 > dp[j])
				dp[i] = dp[j] + 1;
		}
	}

	for (int i = 1; i <= N; i++)
		if (max < dp[i])
			max = dp[i];

	cout << max << "\n";

	return 0;
}

dlwodnsdl 6년 전 1

30번째줄에 조건문에서 dp[j]+1>dp[i]가 아니라 dp[j]+1>dp[j]라 되어 있네요.

furyhunter 6년 전 0

맙소사.. 그랬군요.. 이게 왜 안보였지..

예제 몇개 돌려봤는데 결과가 똑같아서 전혀 몰랐네요

감사합니다! 덕분에 해결했습니다!

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

문제

문제

출처

ICPC

LIS 구하는 방법으로 해봤는데.. 틀린 케이스가 있을까요?

furyhunter 6년 전 0

dlwodnsdl 6년 전 1

furyhunter 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말