취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 12758번 문제인 천상용섬이다.
문제는 아래 링크를 확인하자.

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

첫 물체부터 i번째 물체까지의 부분문제를 생각할 때, i번째 물체를 높이 Hj에서 벨 경우의 수들을 알고 있다면, 첫 물체부터 i+1번째 물체까지의 부분문제에서 i+1번째 물체의 높이의 각 약수 Hk에서 벨 경우의 수는 i번째 물체를 Hk 이하인 높이로 벨 수 있는 경우의 수들의 합으로 구해낼 수 있다.

주어지는 물체의 높이 H는 100만 이하이므로, sqrt(H)까지의 모든 자연수로 직접 나눠보면서 H의 약수 k를 찾았을 때 H/k 또한 약수로 집어넣어주는 식의 간단한 구현으로도 문제를 충분히 해결할 수 있다.

벡터와 swap을 이용하여 불필요한 메모리와 데이터 복사 시간을 절약하자.

아래는 제출한 소스코드이다.

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

vector<int> G[1000001];
vector<pair<int, int>> cur;
vector<pair<int, int>> nxt;

void solve() {
	cur.clear();
	cur.emplace_back(make_pair(1, 1));
	
	int K; cin >> K;
	while (K--) {
		int x; cin >> x;
		if (G[x].empty()) {
			int i = 1;
			for (; i * i < x; i++) {
				if (x % i == 0) {
					G[x].emplace_back(i);
					G[x].emplace_back(x / i);
				}
			}
			if (i * i == x) G[x].emplace_back(i);
			sort(G[x].begin(), G[x].end());
		}

		int cursize = cur.size(), Gxsize = G[x].size();
		int curi = 0, Gxi = 0;
		int cursum = 0;
		while (curi < cursize && Gxi < Gxsize) {
			if (G[x][Gxi] >= cur[curi].first) {
				cursum += cur[curi].second;
				if (cursum > 1000000006) cursum -= 1000000007;
				curi++;
			}
			else {
				nxt.emplace_back(make_pair(G[x][Gxi], cursum));
				Gxi++;
			}
		}
		while (Gxi < Gxsize) {
			nxt.emplace_back(make_pair(G[x][Gxi], cursum));
			Gxi++;
		}
		cur.clear();
		swap(cur, nxt);
	}

	int ans = 0;
	for (auto& p : cur) {
		ans += p.second;
		if (ans > 1000000006) ans -= 1000000007;
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	G[1].emplace_back(1);

	int T; cin >> T;
	while (T--) solve();
}