글 읽기 - 11053 가장 긴 증가하는 부분수열 문제 접근 방법

tkdrnjs67 3년 전 0

일단 틀린것을 알긴 알겠는데, 문제 접근 방법을 잘 생각이 안나서 질문을 올립니다..

처음에 생각은 전에 있는 값이 크다면, 그 이전의 최댓값 + 1을 하고, 그렇지 않다면, 이전의 값을 그대로 넣어 접근하면

결국 끝까지 갔을 떄, 부분 수열의 최댓값이 나올거라고 생각했는데 일부 반례는 맞지만, 틀렸다고 뜹니다..

일단 저의 접근 방법이 잘못되었던 것 같은데 어떻게 해결하면 좋을까요..?

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

int number;
const int SIZE = 1001;
int sequence[SIZE] = { 0, };
int memo[SIZE] = { 0, };

int main() {
	cin >> number;
	for (int i = 1; i <= number; i++) {
		cin >> sequence[i];
		memo[i] = (sequence[i] > sequence[i - 1]) ? memo[i - 1] + 1 : memo[i - 1];
	}
	cout << memo[number];
	return 0;
}

flol47 3년 전 0

알기 쉬운 반례를 드릴테니 잘 생각해보세요

4
10 20 10 20

flol47 3년 전 0

힌트를 드리자면 바로 이전의 값을 가지고만 비교하시면 안됩니다

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

문제

문제

출처

ICPC

11053 가장 긴 증가하는 부분수열 문제 접근 방법

tkdrnjs67 3년 전 0

flol47 3년 전 0

flol47 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말