c언어/백준 11053

 

링크 : 백준 11053] C++ 가장 긴 증가하는 부분 순열 (tistory.com)

백준 11053] C++ 가장 긴 증가하는 부분 순열

 

 

바로 아래 코드가 위 그림을 보고 구현한 코드이다.

for (int j = 0; j < n; j++) {
	// dp[j] = 1; <== 1로 초기화 하면 max 에 1을 더해주지 않아도 답이 잘 나오는데
	//                백준에 올리면 99%에서 틀리다고 나온다. 
	for (int k = 0; k < j; k++) {
		if (arr[j] > arr[k] && dp[k] + 1 > dp[j]) {
			dp[j] = dp[k] + 1;
		}
		if (max < dp[j]) max = dp[j];
	}
}

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>


int main() {

	int dp[1002]  = { 0, };

	int n;
	int max = 0;

	scanf("%d", &n);

	int* arr = (int*)malloc(sizeof(int) * n); //동적할당시 arr의 범위는 * n이므로
						  //for문 사용시 0 ~ n - 1 까지의 인덱스만
						  //사용해야 한다.

	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	for (int j = 0; j < n; j++) {
		for (int k = 0; k < j; k++) {
			if (arr[j] > arr[k] && dp[k] + 1 > dp[j]) {
				dp[j] = dp[k] + 1;
			}
			if (max < dp[j]) max = dp[j];
		}
	}

	printf("%d", max + 1);
}

 

의문점 : dp[j] = 1; 로 초기화 하면 어디에서 틀리는지?