글 읽기 - 반례가 무엇일까요 ᅲᅲ

(追記) (追記ここまで)

반례가 무엇일까요 ᅲᅲ

1912번 - 연속합

ahoy 1년 전 0

질문의 반례들도 거의 다 넣어봤는데, 60퍼에서 틀렸다고 뜹니다 ᅲᅲ 반례가 무엇일까요..

#include <iostream>
#include <climits>
using namespace std;
int n;
int arr[100001]; // 입력값을 저장하는 배열
int cum_sum[100001]; // 현재까지의 누적합을 저장하는 배열 (누적합이 음수가 되는 경우 다음 누적합은 새로운 arr 부터 시작)
int sum_max; // 현재 연속합의 최댓값
bool neg_flag = false; // 누적합이 음수가 되는 경우를 판단하는 변수
int main()
{
 ios::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 cin >> n;
 for (int i = 1; i <= n; i++)
 cin >> arr[i];
 // 초기값 정하기 : 사실 생각해보면 1-index에서는 (i - 1)이 점화식 항에 포함된 경우 딱히 안해줘도 되긴함ᄂ
 cum_sum[1] = arr[1];
 sum_max = arr[1];
 // 초기값을 정해주고 neg_flag를 확인 안해주면, [-1 1] 이 들어온 경우 1이 아닌 0이 최댓값이 되버림
 if (cum_sum[1] < 0)
 neg_flag = true;
 for (int i = 2; i <= n; i++)
 {
 if (neg_flag == true)
 {
 if (arr[i] < 0) // 여전히 arr[i] 가 음수인 경우, 다음 i로 넘어감
 continue;
 else // arr[i]가 음수가 아닌 경우, 누적합을 현재 arr[i]부터 새로 계산
 {
 cum_sum[i] = arr[i];
 neg_flag = false;
 if (sum_max < cum_sum[i]) // 연속합의 최댓값을 비교
 sum_max = cum_sum[i];
 }
 }
 else
 {
 cum_sum[i] = cum_sum[i - 1] + arr[i]; // 누적합 계산
 if (sum_max < cum_sum[i]) // 연속합의 최댓값을 비교
 sum_max = cum_sum[i];
 if (cum_sum[i] < 0) // 누적합이 음수가 되는 순간 neg_flag를 true로 바꿔서 다음 반복문에서 새로운 누적합 계산
 neg_flag = true;
 }
 }
 cout << sum_max;
 return 0;
}

doju 1년 전 1

2
-2 -1

ahoy 1년 전 0

감사합니다 !! 아래와 같이 해결하였습니다

#include <iostream>
using namespace std;
int n;
int arr[100001]; // 입력값을 저장하는 배열
int cum_sum[100001]; // 현재까지의 누적합을 저장하는 배열 (누적합이 음수가 되는 경우 다음 누적합은 새로운 arr 부터 시작)
int sum_max; // 현재 연속합의 최댓값
bool neg_flag = false; // 누적합이 음수가 되는 경우를 판단하는 변수
int main()
{
 ios::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 cin >> n;
 for (int i = 1; i <= n; i++)
 cin >> arr[i];
 // 초기값 정하기 : 사실 생각해보면 1-index에서는 (i - 1)이 점화식 항에 포함된 경우 딱히 안해줘도 되긴함
 cum_sum[1] = arr[1];
 sum_max = arr[1];
 // 초기값을 정해주고 neg_flag를 확인 안해주면, [-1 1] 이 들어온 경우 1이 아닌 0이 최댓값이 되버림
 if (cum_sum[1] < 0)
 neg_flag = true;
 for (int i = 2; i <= n; i++)
 {
 if (neg_flag == true)
 {
 cum_sum[i] = arr[i];
 sum_max = max(sum_max, cum_sum[i]); // 연속합의 최댓값을 비교
 if (cum_sum[i] >= 0)
 neg_flag = false;
 }
 else
 {
 cum_sum[i] = cum_sum[i - 1] + arr[i]; // 누적합 계산
 if (cum_sum[i] < 0) // 누적합이 음수가 되는 순간 neg_flag를 true로 바꿔서 다음 반복문에서 새로운 누적합 계산
 neg_flag = true;
 else
 sum_max = max(sum_max, cum_sum[i]); // 연속합의 최댓값을 비교
 }
 }
 cout << sum_max;
 return 0;
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

반례가 무엇일까요 ᅲᅲ

ahoy 1년 전 0

doju 1년 전 1

ahoy 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말