c언어 11722번 가장 긴 감소하는 부분 수열 (백준)

https://www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

 

 

 

 

#include <stdio.h>

int main(void)
{
	int n = 0;
	int dp[1001] = {0}; //dp (여기선 수열의 길이)
	int tmp[1001] = {0}; //입력받음
	int max = 1; //길이의 최댓값을 담는 변수
	scanf("%d", &n); //몇 개?
	for(int i = 0; i<n; i++) //n만큼 입력받는다.
	{
		scanf("%d", &tmp[i]); //tmp[i]에 입력받음
		dp[i] = 1; //무조건 길이는 1 이상이므로 1을 대입
		for(int j = 0; j<i; j++) //전에 입력받은 것을 다 비교함
		{
			if(tmp[j] > tmp[i]) //전에 입력받은 것이 지금 것 보다 크면
			{
				if(dp[i] < dp[j]+1) 이전의 길이에 1을 더한 것 보다 지금의 수열의 길이가 작으면,
				{
					dp[i] = dp[j]+1; //이것을 그대로 대입함
					if(max < dp[i]) //만약 기존에 가장 길었던 수열의 길이보다 크면,
					max = dp[i]; //길이의 최댓값을 바꿈
				}
			}
		}
	}
	printf("%d", max); //수열의 길이의 최댓값을 출력
	
	return 0;
}

 

핵심 

 

if(tmp[j] > tmp[i])

{

    if(dp[i] < dp[j] + 1)

    {

        dp[i] = dp[j] + 1;

    }

}

 

핵심 부분 풀이

 

입력받은 수 보다 이전의 값이 더 크면, 지금 입력받는 곳의 수열의 길이는 반드시 1 증가한다.

 

그래서 이를 이전의 값까지의 수열의 길이 + 1 로 본 뒤, 이 값이 지금까지의 수열의 길이보다 크면, 대입시켰다.

 

ex)

3 

3 5 2

dp[0] = 1;

dp[1] = 1;

dp[2]은 tmp[0] > tmp[2] 이므로 dp[2] < dp[0] + 1 => 1 < 1 + 1  이므로, 1 < 2 => dp[2] = 2 이다.

dp[2]은 tmp[1] > tmp[2] 이므로 dp[2] < dp[1] + 1 => 2 < 1 + 1 이므로, 성립하지 않아, dp[2]은 그대로 2이다.