글 읽기 - 틀린 곳을 못 찾겠습니다.

papayetoo 4년 전 0

게시판에 있는 test case는 웬만한 것들은 다 찾아서 돌려봤는데 이상이 없습니다.

#include <iostream>
#include <algorithm>
#define MAX 1001
using namespace std;

int main(){

  cin.tie(NULL);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;

  int arr[MAX];
  arr[0] = 0;
  for(int i = 1; i <=n; i++){
    cin >> arr[i];
    //입력을 1~n 까지 사용
  }

  int ans[MAX];
  ans[0] = 0;
  ans[1] = 1;
  for(int i = 2; i <= n; i++){
    if(arr[i] < arr[i-1]){
      //i 번째 수가 그 전 수보다 작을 때
      int j = i - 1;
      while(arr[j] > arr[i]) j--;
      // arr[j] 가 arr[i]보다 큰 마지막 경계 지점까지 이동
      if(arr[j] == arr[i])//arr[i]와 arr[j] 같을 때
        ans[i] = ans[j];
      else //arr[i]가 arr[j]보다 클 때
        ans[i] = ans[j] + 1;
    }else if(arr[i] > arr[i-1]){

      int max = 0;
      for(int j = 1; j <= i -1 ; j++){
        // 1~ i-1까지 중에서 아래의 조건을 만족하는 ans 중 최대값을 찾음.
        if(max <= ans[j] && arr[j] < arr[i]){
          max = ans[j];
        }
      }
    
      ans[i] = max + 1;
    }
  }


  int answer = *max_element(ans+1, ans+n+1);
  cout << answer;
  
  
  return 0;
}

djm03178 4년 전 0

반례입니다.

6
1 2 1 4 3 4

papayetoo 4년 전 0

해결했습니다. arr[i]가 arr[i-1] 클 때 작을 때로 나눠 풀 필요가 없었네요 감사합니다.

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

문제

문제

출처

ICPC

틀린 곳을 못 찾겠습니다.

papayetoo 4년 전 0

djm03178 4년 전 0

papayetoo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말