글 읽기 - c++) 틀리는 이유가 궁금합니다.

kkkj0410 1년 전 0

22번째 줄에 for 범위를 "int j = 1; j<=i; j++"로 잡으면 틀리는 이유가 궁금합니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() 
{
  int arr[1001] = {0,};
  int dp[1001] = {0,};

  int N;
  cin >> N;
  
  for(int i = 1; i<=N; i++)
    {
      cin >> arr[i];
    }
  dp[1] = 1;
  
  int result = dp[1];
  for(int i = 2; i<=N; i++)
    {
      // (아래 범위를 int j = 1; j<=i; j++로 잡으면 틀리는 이유가 궁금함)
      for(int j = i-1; j>=0; j--)
        {
          if(arr[i] > arr[j])
          {
             dp[i] = max(dp[i], dp[j]+1);
          }
        }
      result = max(dp[i], result);
    }
  cout << result;
}

seawon0808 1년 전 1

j는 0이 될 수도 있는데 1까지 밖에 포함을 해서 틀린 것 같습니다.

kokosoko59 1년 전 1

i 앞에 있는 모든 j 중에서 arr[i] > arr[j] 가 없을 때는 dp[i] 에 1 이 들어가야합니다. 그 숫자 자체가 길이 1인 수열이니까요. 그런데 j를 1부터 시작하면 그런 경우에 dp에 아무값도 넣지 않게 되고 따라서 dp[i] 가 0이 됩니다.

그런데 두번째 코드에서 for(int j = i-1; j>=0; j--) 이렇게 쓰시면 j=0일때를 확인하게 되는데 arr[0] 이 0이고 dp[0] 은 0 이기 때문에 arr[i]가 아무리 작아도 항상 24번 포문에 들어가고 따라서 dp[i]=1 로 값이 제대로 들어가게 됩니다.

아마도 int j = 0; j<=i; j++ 이렇게 바꾸면 잘 돌아가지 않을까 싶네요

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

문제

문제

출처

ICPC

c++) 틀리는 이유가 궁금합니다.

kkkj0410 1년 전 0

seawon0808 1년 전 1

kokosoko59 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말