[백준 28437번] 막대 만들기 C++ 풀이

지난 6일에 열린 백준아레나에서 풀지 못한 문제로 업솔빙하려고 한다.

1.문제

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

28437번: 막대 만들기

문제를 요약하면 주어진 숫자 $ A_1,, A_n $ 으로 가지고 $ L_1,, L_Q $의 각각의 숫자에 대해서 만들 수 있는 경우의 수를 구해야한다. 이때 $ A_1,, A_n $ 의 숫자를 하나 선택해서 곱셈연산을 원하는 만큼 할 수 있다.(곱셈연산이 다르면 다른경우로 분류할수 있다)

예를 들어 $ 1 $를 가지고 $8$을 만든다고 했을때 $ 1->2->8 $(2와 4를 곱함) 와 $ 1->8 $(8을 곱함)은 서로 다른경우이다.

 

2.접근

$dp[i]$를 $i$를 만들 수 있는 모든 경우의 수라고 할때,

$dp[i]=dp[a_1]+dp[a_2]+...+dp[a_k]$ 이다($a_k$는 $i$의 약수이고, 각각이 서로 다른 방법임이 보장된다.)

top-down, buttom-up 방식으로 구현하면 된다.

시간 복잡도: $O(NlogN+Q)$

 

3.풀이

#include<iostream>

using namespace std;
int dp[100001] = { 0 };
int arr[100001] = { 0 };
int result[100001] = { 0 };
int N, Q;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int temp;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> temp;
		dp[temp]++;

	}
	for (int i = 1; i <= 100000; i++) {
		if (dp[i] == 0)
			continue;
		temp = i+i;
		while (temp<=100000) {
			dp[temp] += dp[i];
			temp += i;
		}
	}
	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> temp;
		result[i] = dp[temp];
	}
	for (int i = 1; i <= Q; i++)
		cout << result[i] << " ";


	return 0;
}

 

시간복잡도를 잘못계산해서 위의 방법의 시간초과된다고 판단해서 풀지못했는데 다음부터는 시간복잡도를 더 꼼꼼히 계산해야겠다..