https://www.acmicpc.net/problem/28437
문제
> 길고 얇은 막대를 만드는 과정은 다음과 같습니다.
> 기본으로 사용할 막대를 고릅니다.
> 사용 가능한 막대의 길이는 A_1,.. A_N입니다.
> 원하는 길이가 될 때까지 0번 이상 막대를 늘립니다.
> 기계에 2 이상의 양의 정수 k를 설정해서 막대를 넣으면,
길이가 x였던 막대가 길이 kx의 막대가 됩니다.
> 주어진 Q개의 길이 각각에 대해 길이가 L_i인 막대를 만드는 방법의 수를 출력하세요.
> 두 방법이 서로 다르다는 것은 처음 선택한 막대가 다르거나,
막대를 늘리는 과정에서 입력한 정수 k의 수열이 서로 다르다는 것을 의미합니다.접근
만들어야할 막대의 길이가 최대 100,000이다. 이 길이를 만들려면 최소 1짜리 막대에 대해 100,000배 했을 때, 2짜리를 50,000배, 4 짜리 25,000배...이런식으로 간다.
문제에서 2x3과 3x2는 각각 다른경우로 친다고 하였으니 즉, 1부터 100,000까지 두 수의 곱의 모든 경우를 구해주면 된다. 예를 들어 4를 만들려면 1x4, 1x2x2, 2x2, 4x1이 있다. 이는 dp(1)을 4배, dp(1)을 두배해서 만든 dp(2)의 2배, dp(2)의 2배, dp(4)의 1배 이다. 따라서 길이 4에 대한 dp(4)는 dp(1)=1 + dp(2)=2 + dp(4)=1 해서 4가지가 나오게 된다. 이를 수식으로 쓰면 i=1~100000까지, j=2~ㅓxi<=100000까지 반복하며 dp(ixj) += dp(i)를 누적시켜주면 된다.
문제해결
> 가지고있는 막대를 Astick에, 만들어야할 막대를 Lstick에 저장하고, Lstick중 가장 긴 막대를 잡아 LonS에 저장한다.
> 가장 긴 막대 이상의 막대는 만들 필요가 없으므로 dp의 크기를 LongS+1만큼 만들어준다.
> 이제 가지고있는 막대에 대해 전부 돌며 자기자신을 만드는 경우를 고려해서 초기값을 1로 준다.
> 이때, 젤 긴 막대보다 긴 막대는 쓸 일이 없기 때문에 조건문으로 걸러준다.
> 이제 예외없는 모든 경우를 따져주기 위해 가진 막대중에서가 아닌 1부터 가장 긴 막대의 길이까지 반복문을 돈다.
> 돌면서 dp(i)가 0이면 스킵한다. 이는 i라는 길이의 막대를 만들 방법이 0이라는 뜻이므로 못쓰는 막대라 불가능한 경우를 제한것이다.
> 이제 앞에서 초기값으로 1을 줬기 때문에 2부터 시작하며 i*j가 젤 긴 막대를 넘어가는 불필요한 연산을 제거해준다.
> dp(i*j) += dp(i)로 i길이 막대를 j배 했을 때의 모든 결과인 dp(i*j)에 dp(i)를 누적해준다.
> 필요한 결과인 Lstick에 관한 경우만 골라서 출력해준다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, Q;
vector<int> Astick;
vector<int> Lstick;
vector<int> dp;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
Astick.resize(N);
for (int i = 0; i < N; i++) cin >> Astick[i];
cin >> Q;
Lstick.resize(Q);
int LongS = 0;
for (int i = 0; i < Q; i++)
{
cin >> Lstick[i];
LongS = max(LongS, Lstick[i]);
}
dp.resize(LongS + 1, 0);
for (auto a : Astick)
{
if (a > LongS) continue;
dp[a] = 1;
}
for (int i = 1; i <= LongS; i++)
{
if (dp[i] == 0) continue;
for (int j = 2; j * i <= LongS; j++)
{
dp[i * j] += dp[i];
}
}
for (int i = 0; i < Q; i++) cout << dp[Lstick[i]] << " ";
}
후기
dp(ixj)를 구하는 부분을 이해하는게 어려웠다. 처음엔 입력받은 처음에 들고있는 막대로만 만드는 경우를 따졌었다.
근데 예외가 발생하며 틀렸다. 예시를 바꿔서 하나씩 써보니
입력이 1,3,4로 1,2,3,4,5,6을 만든다고 치자.
그럼 1x2, 1x3, 1x4, 1x5, 1x6 전부 += dp(1)하고, 다음은 3x2로 끝나게 된다. 그럼 dp(4)엔 총 2가 남는다. 하지만 문제에서 원하는건 1x2x2의 경우도 따져야하고, 2x3의 경우도 따져야한다. 이게 비어있는거다.
