[SW Expert Academy] 9708. 가장 긴 수열 D4

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXDNGXlKagUDFAVX&categoryId=AXDNGXlKagUDFAVX&categoryType=CODE

 

 

문제 풀이:

1 ≤ i < K인 i에 대해 $a_i < a_{i+1}$ 이면서, $a_i$이 $a_{i+1}$의 약수여야 한다.

$a_0$, $a_1$, $a_2$가 위 조건을 만족한다면,

$a_0$*k=$a_1$

$a_0$*r=$a_2$ 이다.

 

즉,

$a_0$를 포함하려면, 각 값들은 $a_0$의 배수인 것!

 

for문을 돌면서, 현재 arr [i] 값을 약수로 두는 값을 찾기 위해, $a_0$*2, $a_0$*3, $a_0$*4 해가며 해당 위치에서 가능한 가장 긴 수열 길이를 증가시킨다.

 

 

소스 코드:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define inf 987654321
using namespace std;


typedef pair<int, int> P;
typedef long long ll;
int tc, n, res,arr[100001],dp[1000001];

void func(stack<int> st, int pos) {
	
	res = max(res, int(st.size()));
	if (pos == n) return;
	
	if (st.empty()||arr[pos] % st.top() == 0) {
		st.push(arr[pos]);
		return func(st, pos + 1);
	}
	
	//선택 안 하기
	func(st, pos + 1);

	//전 값 지우고, 현재 값 넣기
	while (!st.empty()) {
		st.pop();
		if (arr[pos] % st.top() == 0) {
			st.push(arr[pos]);
			return func(st, pos + 1);
		}
	}
	st.push(arr[pos]);
	return func(st, pos + 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;

	for (int i = 1; i <= tc; i++) {
		cin >> n ;
		stack<int> st;
		res = 1;

		memset(dp, 0, sizeof(dp));
		for (int j = 0; j < n; j++) {
			cin >> arr[j];
			dp[arr[j]] = 1;
		}
		sort(arr, arr + n);
		
		for (int i = 0; i < n; i++) {
			int tmp = arr[i]+arr[i];
			while (tmp <= arr[n - 1]) {
				if (dp[tmp]&&tmp % arr[i] == 0) {
					dp[tmp] = max(dp[tmp],dp[arr[i]] + 1);
					res = max(res, dp[tmp]);
				}
				tmp += arr[i];
			}
		}
		cout << "#" << i << " " << res<< '\n';
	}
	return 0;
}