[C언어] 백준 11053 : 가장 긴 증가하는 부분 수열

생각의 흐름

LIS가 뭔지 몰라서 검색했다.
https://rebro.kr/33
LIS는 코딩테스트에서 자주 나오는 유형이고, 푸는 방법은 크게 두가지가 있다. DP와 이분 탐색이다. 먼저 DP는 n값이 커질수록 시간이 굉장히 오래 걸리는 방법이고, 이분탐색은 시간절약이 잘 되어 결국에는 이분 탐색을 사용한다고 설명이 되어있다.

이분탐색도 검색해보았지만, 아직 너무 어려워 DP로 풀기로 했다.

틀렸던 풀이

#include <stdio.h>

int main()
{
	int n;
	int dp[1001] = {0, };
	int input[1001] = {0, };
	int max = 0;
	scanf("%d", &n); // 4로 가정
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &input[i]); // 10 20 30 15 으로 가정,
		if (dp[i] == 0)
			dp[i] = 1; // 기본값 1 넣어줌
		for (int j = 0; j < i; j++)
		{
			if (input[i] > input[j]) // i = 1일때로 예를 들면, 20은 10보다 크므로 if에 걸림
			{
				if (dp[i] < dp[j] + 1) // dp[1] = 1, dp[0] + 1 = 2이므로 if에 걸림
				{
					dp[i] = dp[j] + 1; // dp[1] = 2
					if (max < dp[i]) // 우리는 최대 길이를 구하기에 max를 구해야함. dp[i]가 max보다 클 경우
						max = dp[i]; // max에 dp[i]를 저장, 계속 반복
				}
			}
		}
	}
	printf("%d", max); // max출력
}

수정한 풀이

#include <stdio.h>

int main()
{
	int n;
	int dp[1001] = {0, };
	int input[1001] = {0, };
	int max = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &input[i]);
		for (int j = 0; j < i; j++)
		{
			if (input[i] > input[j])
			{
				if (dp[i] < dp[j] + 1)
				{
					dp[i] = dp[j] + 1;
					if (max < dp[i])
						max = dp[i];
				}
			}
		}
	}
	printf("%d", max);
}

틀렸던 풀이와 수정한 풀이의 차이점이
for문 i = 1; i<= n; i++ 로 바꿔주고,
if (dp[i] == 0)
dp[i] = 1; // 기본값 1 넣어줌
이 부분을 그냥 지워버렸더니 통과했다. 아직도 왜 통과했는지 모르겠다.

심지어 내일 LIS다시풀어보라해도 설명하면서 풀 수 있을 지 모르겠다.

일단 백준 질문게시판에 올려놨으니, 답변이 오면 피드백하고 수정해야겠다.
그 다음문제 골드3이던데 LIS를 활용하는 문제이다. 지금은 어려울 것 같다.. 그동안 다른걸 공부하자.

https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-11053%EB%B2%88-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-CC

https://henrynoh.tistory.com/32