[DP,백트래킹] 백준 문제 풀이 - 14002 가장 긴 증가하는 부분 수열 4

👩🏻‍💻 문제링크

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

14002번: 가장 긴 증가하는 부분 수열 4

 

✍️ 아이디어

1. 문제 이해

• 부분수열 1에서 수열을 출력하는것 까지 함

2. 저장할 배열을 하나 더 만들어서 어떠한 값 때문에 자신의 값이 1 증가 했는지 인덱스를 기록 = 백트래킹

3. 백트래킹 : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.

✍️소스코드

• 나의코드 : 백트래킹 미사용 - 테스트케이스 답은 나오는데 백준에선 틀림
• 1이 증가하게 된 원인을 따로 배열에 기록

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

int result[1001];

int main()
{
	int n; cin>>n;
	int arr[n+1]={0};
	int idx[n+1]={0};
	
	stack <int> s;
	for(int i=1; i<=n; i++)
	{
		cin>>arr[i];
	}
	result[1]=1;
	for(int i=2; i<=n; i++)
	{
		result[i]=1;
		int max=0;
		for(int j=1; j<i; j++)
		{
			if(arr[i]<=arr[j])
			{
				continue;
			}
			if(max<result[j])
			{
				max=result[j];
				idx[i]=j;
			}
		}
		result[i]+=max;
	}
	int top_result;
	top_result=*max_element(result, result+n+1);
	cout<<top_result<<'\n';
	int top_idx;
	for(int i=1; i<=n; i++)
	{
		if(top_result==result[i])
			top_idx=i;
	}
	while(1)
	{
		s.push(arr[top_idx]);
		top_idx=idx[top_idx];
		if(idx[top_idx]==0) break;
	}
	s.push(arr[top_idx]);
	while(!s.empty())
	{
		cout<<s.top()<<' ';
		s.pop();
	}
    cout<<'\n';
}

 

 

• 다른 사람의 코드

#include <iostream>
using namespace std;
int a[1000];
int d[1000];
int v[1000];
void go(int p) {
    // ? -> ? -> ... a[v[p]] -> a[p]
    // ---------------------
    //        go(v[p]);
    if (p == -1) {
        return ;
    }
    go(v[p]);
    cout << a[p] << ' ';
}
int main() {
    int n;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }
    for (int i=0; i<n; i++) {
        d[i] = 1;
        v[i] = -1;
        for (int j=0; j<i; j++) {
            if (a[j] < a[i] && d[i] < d[j]+1) {
                d[i] = d[j]+1;
                v[i] = j;
            }
        }
    }
    int ans = d[0];
    int p = 0;
    for (int i=0; i<n; i++) {
        if (ans < d[i]) {
            ans = d[i];
            p = i;
        }
    }
    cout << ans << '\n';
    go(p);
    cout << '\n';
    return 0;
}

 

체감난이도	걸린시간	참고	사용 문법
상	1hour	강의 참고	DP, 백트래킹