글 읽기 - 올려주신 반례도 맞는데 어디서 틀린걸까요ㅜ

wjdghks94k 3년 전 0

로직은 맞다고 생각합니다.

굳이 이 코드를 고집해보고 싶은 오기가 생기네요.

혹시 어디서 틀렸을까요?

이것도 되는거 같은데..

#include <iostream>
using namespace std;

int n;
int arr[1001];
int dp[1001];

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	dp[0] = arr[0];

	//맨 앞이 젤 작지 않을수 있음
	//8 1 8 같은 경우 dp[1]=1이 되야함. flag로 최초 값인지 체크
	for (int i = 1; i < n; i++) {
		bool flag = false; 
		for (int j = i - 1; j >= 0; j--) {
			if (arr[i] > arr[j]) {
				dp[i] = dp[j] + arr[i];
				flag = true;
				break;
			}
		}
		if (flag == false)
			dp[i] = arr[i];
	}

	//가장 큰 증가 부분 수열 구하기
	int result = 0;
	for (int i = 0; i < n; i++) {
		if (dp[i] >= result) result = dp[i];
	}
	cout << result;
	return 0;
}

djs100201 3년 전 0

30 20 10 40

ans:70

output:50

dp[i]값과 dp[j] + arr[i]값을 비교한 후 갱신해주어야 합니다

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

문제

문제

출처

ICPC

올려주신 반례도 맞는데 어디서 틀린걸까요ㅜ

wjdghks94k 3년 전 0

djs100201 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말