글 읽기 - 혹시 안되는 예시좀 찾아주실 수 있으신가요...

lenyh 7년 전 2

오름차순으로 정렬해서 이어지는 구간을 조사한다면 최솟값이 나올수 밖에 없다고 생각하고 부분합 써서 계산한건데..

혹시 안되는 예시좀 찾아주실 수 있으신가요..?

아니면 아예 그냥 접근 자체가 틀린걸까요...

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
int a[101];
int psum[101];
int comp(int a, int b){
	int cnt=0;
	if (a >= b){
		cnt = a - b;
		return cnt;
	}
	else{
		cnt = b - a;
		return cnt;
	}
}
int main(){
	int to,k, j, total=0, hibi=0, opp=0, ans=450000, cnt=0, r1=0, r2=0, temp=0;
		scanf("%d", &to);
		for (j = 1; j <= to; j++){
			scanf("%d", &a[j]);
			total += a[j];
		}
    //정렬
		for (j = 1; j < to; j++){
			for (k = j + 1; k <= to; k++){
				if (a[j] > a[k]){
					temp = a[j];
					a[j] = a[k];
					a[k] = temp;
				}
			}
		}
	//부분합
        for (j = 1; j <= to; j++){
	    		psum[j] = psum[j - 1] + a[j];
	    	}
	//비교
        for (j = 0; j < to; j++){
			for (k = j + 1; k <= to; k++){
				hibi = psum[k] - psum[j];
				opp = total - hibi;
				cnt = comp(hibi, opp);
				if (cnt <= ans) {
					ans = cnt;
					r1 = hibi;
					r2 = opp;
				}
			}
        }
			if (r1 <= r2) {
				printf("%d %d", r1, r2);
			}
			else{
				printf("%d %d", r2, r1);
            }
	return 0;
}

/* <왜 틀렸니?>



*/

noru0114 7년 전 0

부분합으로 아예안될걸요

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

문제

문제

출처

ICPC

혹시 안되는 예시좀 찾아주실 수 있으신가요...

lenyh 7년 전 2

noru0114 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말