BOJ 11053번 :: 가장 긴 증가하는 부분수열

#문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

#작성 코드

#include <iostream>
using namespace std;

int N;
int A[1001];	// N최대값 1000이므로. 인덱스 1~1000 사용

// 수열 A의 i번째 수까지 증가하는 부분 수열의 원소 개수
int d[1001]; 

int solve(){
	int result=0;
	
	for(int i=1; i<=N; i++){
		// i번째 수 이전의 수들 중에서 A[i]보다 작은 수에 대해 조사. 
		for(int j=1; j<i; j++){
			if( A[i] > A[j] ){
				// i번째 수까지의 증가 수열의 길이
				// = i이전에 A[i]보다 작은 수까지의 증가 수열의 길이 + 1 (i를포함시킨다.) 
				d[i] = max( d[i], d[j]+1 );
			}
		}
		// d[i]를 갱신하면서, result에 가장 큰 d[i]를 갱신한다. 
		result = max(result, d[i]);
	}
	return result;	// 가장 긴 증가수열의 길이를 리턴. 
}

int main(){
	// 수열의 원소 개수 입력. 
	cin>>N;
	// N개의 원소 입력. 
	for(int i=1; i<=N; i++){
		cin>>A[i];
	}	
    // d[1001] 전역배열의 원소를 모두 1로 초기화한다.
	fill_n(d, 1001, 1);
    
	cout<<solve()<<"\n";
	return 0;
} 

##

전역배열을 모두 1로 초기화하려고  int d[1001] = {1, }; 코드를 사용하였는데, 이것때문에 틀렸음을 알았다

위의 코드는 배열의 첫 번째 원소만 1로 초기화하고 나머지는 모두 0으로 초기화되기 때문에 원하는 결과를 얻을 수 없었다.

https://shjz.tistory.com/38 에서 배열을 초기화 하는 방법을 찾았다.

int d[1001]; 으로 전역 배열을 선언하고,

std::fill_n(d, 1001, 1); 으로 main 함수 내에서 초기화하는 방법을 사용해야겠다.