글 읽기 - 이 알고리즘에서 어떤 부분이 문제인지 궁금합니다.

rla6431078 6년 전 0

제가 테스트 케이스 만들어서 돌려보면 다 맞는데

돌려보면 틀리다고 나옵니다.

혹시 예외 케이스나

알고리즘 어느 부분이 잘못된건지 알려주세요ㅜ

#include <cstdio>
#include <cstring>

int n, i, max = 0, temp = 0, idx = 1, over = 1;
int left[2001];
int right[2001];

int main(){
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		scanf("%d", &left[i]);
	for (i = 1; i <= n; i++)
		scanf("%d", &right[i]);

	while (idx <= n){
		for (i = over; i <= n; i++){
			if (left[idx] > right[i])
				temp += right[i];
			else{
				for (int j = idx; j <= n; j++){
					if (left[j] > right[i]){
						idx = j;
						break;
					}
				}
				if (left[idx] > right[i]){
					temp += right[i];
					continue;
				}
				else{
					over = i + 1;
					break;
				}
			}

		}
		max = max > temp ? max : temp;
		temp = 0;
		if (idx < i)idx++;
	}
	printf("%d", max);
}

lyzqm 6년 전 0

4
4 1 2 3
5 1 4 2

a, b버림
a버림
b버림 + 1
a, b버림
b버림 + 2
= 답 : 3

2가 나오시네요

이문제는 greedy하게 풀어서 결과값이 최적해가 나온다는 보장이 없습니다.

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

문제

문제

출처

ICPC

이 알고리즘에서 어떤 부분이 문제인지 궁금합니다.

rla6431078 6년 전 0

lyzqm 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말