글 읽기 - 게시판 모든 반례가 통과하는데 시작하자마자 틀렸습니다가 나옵니다.

kjw13 3년 전 0

어떤 반례가 있을까요.. 아니면 구현 방법이 잘못됐을까요

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int n;
vector<int> v;
int arr[1002];
int solve(int idx,vector<int> ans, int way, int point)
{
    if(idx==v.size())
    {
        return ans.size();   
    } 
    vector<int> temp;
    temp = ans;
    if(way==1)
    {
        if(ans[ans.size()-1]<v[idx])
        {
            ans.push_back(v[idx]);
            arr[idx] = solve(idx+1,ans,way,point);  
        }
        else if(ans[ans.size()-1]>v[idx])
        {
            temp = ans;
            int num = v[idx];
            ans.push_back(v[idx]);
            for (int i = temp.size()-1; i >= 0; --i)
            {
                if(num>temp[i]) temp[i+1] = num;
                else if(i==0) temp[i] = num; 
            }
            arr[idx] = max(solve(idx+1,ans,0,ans.size()-1),solve(idx+1,temp,way,0));
        }
        else arr[idx] = solve(idx+1,ans,way,point);
    }
    else
    {
        if(ans[ans.size()-1]>v[idx])
        {
            ans.push_back(v[idx]);
            arr[idx] = solve(idx+1,ans,way,point);  
        }
        else if(ans[ans.size()-1]<v[idx])
        {
            temp = ans;
            int num = v[idx];
            for (int i = temp.size()-1; i >= point; --i)
            {
                if(num<temp[i]) temp[i+1] = num;
                else if(i==point&&num<temp[i-1]) temp[i] = num; 
            }
            arr[idx] = solve(idx+1,temp,0,point);
        }
        else arr[idx] = solve(idx+1,ans,0,point);         
    }
    return arr[idx]; 
}

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    int num;
    vector<int> ans;
    cin>>n;
    for (int i = 0; i < n; ++i)
    {
        cin>>num;
        v.push_back(num);
    }
    ans.push_back(v[0]);
    cout<<solve(1,ans,1,0)<<"\n";
    return 0;
}

keunbum 3년 전 1

반례 드립니다.

답은

입니다.

10
9 8 6 2 3 5 4 10 1 7

k906506 3년 전 0

↘ keunbum

어떻게 해서 6인건가요?

2 3 4 10 7

2 3 4 10 1

2 3 5 10 7

2 3 5 10 1

5가 맞지 않나요?

keunbum 3년 전 0

9 8 6 5 4 1

이 가능합니다

k906506 3년 전 0

↘ keunbum

수열 S가 어떤 수 S_k를 기준으로 S₁ < S₂ < ... S_k-1 < S_k > S_k+1 > ... S_N-1 > S_N을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

해당 수열은 바이토닉 수열이 아니지 않나요...? 위의 조건을 만족해야합니다.

keunbum 3년 전 0

그런 혼란을 막기 위해 문제에서 예시를 잘 들어 주었습니다.

k의 범위는 1 ~ N으로 봐야 하고,

양쪽의 부등호는 그리고 가 아니라 또는 의 의미로 봐야합니다.

말씀하신 대로 라면 N이 3 이상이어야 하겠지만

그렇지 않습니다.

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

문제

문제

출처

ICPC

게시판 모든 반례가 통과하는데 시작하자마자 틀렸습니다가 나옵니다.

kjw13 3년 전 0

keunbum 3년 전 1

k906506 3년 전 0

keunbum 3년 전 0

k906506 3년 전 0

keunbum 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말