[leetcode][368] Largest Divisible Subset

문제 : https://leetcode.com/problems/largest-divisible-subset/

---

중복되지 않는 양수 정수 배열이 주어질 때, (A, B) pair가 A%B = 0 이거나 B%A = 0 인 경우, 즉, 나누어떨어지는 수들로만 이루어진 subset들 중 가장 긴 subset을 하나 구하는 문제이다.

---

dp로 풀었다.

dp[i] = 부분문자열[i~]에서 i 번째 정수를 반드시 포함하면서 조건에 만족하는 subset들 중 최장 길이. (길이를 저장)

nextInd[i] = dp[i]가 저장될 때, 2번째로 저장되는 정수의 인덱스. (1번째는 i번째 정수로 고정). 나중에 subset 문자열을 구할 때 추적용도로 사용한다. 초기값은 -1

 

[1,2,4,5]을 예로 들어보자.

인덱스 0,1,2,3 을 시작으로 하는 dp[i]를 모두 구한 뒤 최장길이를 가지는 시작인덱스를 구한다.

dp[i]를 구하는 방법은 i가 0이라고 할 때,

다음 인덱스가 될 수 있는 2,4,5를(다음 탐색 인덱스를 next라 하자) 현재 탐색중인 정수 1로 나누어떨어지는지 먼저 체크한다.

나누어떨어지지 않는다면 조건을 만족하지 못하고 나누어떨어진다면 그 수를 시작 인덱스로 하는 dp[next]를 다시 구한다.

만약 이때동안 구한 최대 길이 보다 이번에 구한 dp[next] + 1(1을 더한 이유는 i번째 정수를 포함시켜야 하기 때문)가 더 큰 경우 dp[i]를 dp[next] + 1로 갱신한다. 또한 nextInd[i] 배열 값도 next로 갱신한다.

 

모든 dp 배열을 채웠을 때, 최대값을 가지는 요소의 인덱스가 우리가 구하고자 하는 subset의 시작인덱스(startInd)가 된다.

시작인덱스를 기준으로 ans 배열을 채워나가는데 다음에 넣을 인덱스는 nextInd[startInd]로 구한다.

nextInd 배열 요소가 -1인 경우, 즉, 더 이상 nextInd가 없는 경우 정답 배열이 완성된다.

 

시간복잡도는 dp 배열을 채우는데 걸리는 시간인 O(N^2)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/368.%20Largest%20Divisible%20Subset.cpp