글 읽기 - 아무리 봐도 어디가 틀렸는지 모르겠습니다 ㅜ

oldbook 7년 전 1

i번째 배열이 부분수열의 가장 큰 숫자라 가정하고

1~ i-1 까지 배열의 값이 i번째 보다 작으면 모두 이 부분수열에 포함되므로

sum함수 다 더해줬습니다.

그렇게 1~n 까지 배열에 각각 구해줘서 max 출력해줬습니다.

뭐가 문제일까요 ㅜㅜ

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int kk[1001];
int max[1001];

int main() {
	int n;
	int ans= 0;
	int sum= 0;

	
	scanf("%d", &n);
	for (int i = 1; i < n + 1; i++) { scanf("%d", &kk[i]); }
	
	for (int i = 1; i < n +1; i++) {//인덱스 1~n까지 하나씩 읽고 
		sum = kk[i] ;               //자신의 값보다 먼저 나온 배열의 값이 작으면 다넣어줌
		for (int j = 1; j < i; j++) {
			if (kk[i] > kk[j]) {
				sum += kk[j];
			}
		}
		max[i] = sum;
	}

	ans = max[1];
	for (int i = 1; i < n + 1; i++) {
		if (ans < max[i]) ans = max[i];
	}

	printf("%d", ans);
	return 0;
}

ljh6274 7년 전 2

증가 부분 수열이기 때문에 1~i-1까지 모두 더 하면 안됩니다.

예를 들어

10
1 100 55 50 60 3 5 6 7 8

의 경우에 질문자님 코드에선 1 + 55 + 50 + 60 = 166이 출력되지만

실제 가장 큰 증가 부분 수열은 1 + 55 + 60 으로 116이 정답 입니다.

다이나믹 프로그래밍 방식으로 하셔야 합니다.

d[i]를 i번째까지 최대 증가 부분 수열의 합으로 정의 하시고 이를 이용하시면 됩니다.

oldbook 7년 전 0

아하 !! 그렇군요 ~~!

감사합니다. 한수 배웠습니다.

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

문제

문제

출처

ICPC

아무리 봐도 어디가 틀렸는지 모르겠습니다 ㅜ

oldbook 7년 전 1

ljh6274 7년 전 2

oldbook 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말