글 읽기 - c++반례좀 주세요 ㅠㅠ

wjddbstj98 2년 전 0

앞에 나오는 예시는 다 해봤는데 다 안되요 반례좀 주세요

ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤㅤ ㅤ ㅤ ㅤ ㅤ ㅤㅤㅤㅤㅤ

#include<iostream>
#include<vector>
#include<stdio.h>

using namespace std;

int maxs = 0;   //MAX값

vector<int> v;  //입력 배열
int N,anyNum;   //입력용 변수
int a=0,b=0,c=0;    //3가지 케이스
void Input()    //입력함수
{
    cin >> N;
    for(int i=0;i<N;i++)
    {
        cin >> anyNum;
        v.push_back(anyNum);
    }
}

int main()
{
    Input();
    
    
    for(int i=1;i<N-1;i++)  // 가운데 벌통 이동
    {
        for(int j=1;j<=i;j++)
        {
            a+=v[j];
        }
        for(int j=N-2;j>=i;j--)
        {
            a+=v[j];

        }

        if(maxs<a)
        {
            maxs = a;
        }
        a=0;
    }
    
        
    for(int i=1;i<N-1;i++)  //오른쪽 벌집 이동
    {
        for(int j=1;j<N;j++)
        {
            if(j!=i)
            {
                b+=v[j];
            }
        }
        for(int j=i+1;j<N;j++)
        {
            b+=v[j];
        }
        if(maxs<b)
        {
            maxs = b;
        }
        b=0;
    }
    for(int i=N-2;i>1;i--) //왼쪽 벌집 이동
    {
        for(int j=i;j>0;j--)
        {
            c+=v[j];
        }
        for(int j=N-1;j>0;j--)
        {
            if(j!=i)
            {
                c+=v[j];
            }
        }
        if(maxs<c)
        {
            maxs = c;
        }
        c=0;
    }
    printf("%d",maxs);
}

zigui 2년 전 0

66번째 줄부터 84번째 줄까지의 반복문에 실수가 많이 있네요.

1. 66번째 줄에 i>1을 i>=1로 고쳐야 합니다.
2. 68번째 줄에 j>0을 j>=0로 고쳐야 합니다.
3. 68번째 줄에 j=i을 j=i-1로 고쳐야 합니다.
4. 72번째 줄에 j>1을 j>=1로 고쳐야 합니다.
5. 72번째 줄에 j=N-1을 j=N-2로 고쳐야 합니다.

wjddbstj98 2년 전 0

감사합니다 ㅠㅠ

wjddbstj98 2년 전 0

그런데 100점이라고 뜨지 않고 55점이라고 뜨네요....

zigui 2년 전 0

지금 풀이는 N이 10만일 때 연산을 약 100억번 하게 됩니다. (시간복잡도는 O(N2)입니다) 때문에 마지막 서브태스크에서는 시간초과가 나게 됩니다.

100점을 받기 위해서는 더 효율적인 알고리즘으로 해결해야 합니다.

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

문제

문제

출처

ICPC

c++반례좀 주세요 ㅠㅠ

wjddbstj98 2년 전 0

ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤㅤ ㅤ ㅤ ㅤ ㅤ ㅤㅤㅤㅤㅤ

zigui 2년 전 0

wjddbstj98 2년 전 0

wjddbstj98 2년 전 0

zigui 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말