글 읽기 - 전깃줄, 반례를 찾아주세요

aquarius456 6년 전 0

LIS 방식으로 풀었고 주어진 예제와 질문에 주어진 예제 모두 돌려서 정답이 나왔습니다. 하지만 결과는 시작하자마자 틀렸다고 나오네요. 도와주세요 ㅠ

#include <iostream>
using namespace std;
int arr[501];
int dp[501][501];
inline int MAX(int a, int b) {
	return a > b ? a : b;
}
int main() {
	int n;
	int limit = 0;
	int x, y; 
	int k = 0;
	cin >> n;
	while (n--) {
		cin >> x >> y;
		arr[x] = y;
	}
	for (int i = 1; i <= 500; i++) {
		for (int j = i; j <= 500; j++) {
			if (arr[j] == 0 || arr[i] <= arr[j]) dp[i][j] = MAX(dp[i-1][j], dp[i][j-1]);
			else if (arr[i] > arr[j]) {
				dp[i][j] = MAX(dp[i][j-1], dp[i-1][j-1] +1);
			}
		}
	}
	cout << dp[500][500] << endl;
	return 0; 
}

aquarius456 6년 전 4

반례를 찾았어요;;

1 8

2 9

4 4

5 2

6 1

7 5

계산해 보면 4가 나와야 하지만 제 코드는 3이 나오네요.

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

문제

문제

출처

ICPC

전깃줄, 반례를 찾아주세요

aquarius456 6년 전 0

aquarius456 6년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말