94. 최대 선 연결하기 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★☆☆

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, p1 = 1, p2 = 1, cnt = 0;
	cin >> n;
	
	vector<int> a(n+1, 0);
	vector<int> ch(n+1, 0);
	
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	
	while(p1 <= n)
	{
		for(int i = p2; i <= n; i++)
		{
			if(p1 == a[i])
			{
				p2 = i+1;
				cnt++;
			}
		}
		p1++;
	}
	
	cout << cnt << "\n";
	
	return 0;
}

1. 이미 선이 이어지면 그 숫자 이전에 수와는 연결하면 선이 겹쳐서 안 된다. 그 점을 유의해서 풀면 쉽다.

 

 

다른 풀이(최대 증가수열)

#include <iostream>

using namespace std;

int dy[100];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, res = 0;
	
	cin >> n;
	
	int a[n+1];
	
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	
	dy[1] = 1;
	
	for(int i = 2; i <= n; i++)
	{
		int max = 0;
		for(int j = i-1; j >= 1; j--)
		{
			if(a[j] < a[i] && dy[j] > max)
			{
				max = dy[j];
			}
		}
		dy[i] = max + 1;
		if(dy[i] > res) res = dy[i];
	}
	
	cout << res << "\n";
	
	return 0;
}