첫번째 풀이
위처럼 DP[][0]에는 전 행의 총합이 들어가게 되고, DP[][1]에는 전 열의 값에서 전 행의 전 열의 값을 빼주는 식으로 진행된다
$$ DP[i][j] = DP[i][j-1] - DP[i-1][j-1] $$
→ 이런식으로 코드가 진행이 되면 오버플로우가 난 녀석과 뺄셈이 일어날때 음수의 값이 나오는 등 이상한 결과를 초래하게 된다
#include <iostream>
#include <vector>
int n;
std::vector<std::vector<long long> > dp;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
std::cin >> n;
dp.resize(n + 1, std::vector<long long>(10, 1));
}
void solution()
{
long long sum;
sum = 10;
for (int i = 2; i <= n; i++)
{
dp[i][0] = sum;
for (int j = 1; j <= 9; j++)
{
dp[i][j] = (dp[i][j - 1] - dp[i - 1][j - 1]) % 10007;
sum = (sum + dp[i][j]) % 10007;
}
}
std::cout << sum % 10007;
}
int main(void)
{
input_setting();
input();
solution();
return (0);
}
→라고 생각했는데 분기를 통해서 해결할 수 있었음(THANKS TO CHAN...SUHSHIN...NAJLEE)
if (dp[i][j - 1] < dp[i - 1][j - 1])
dp[i][j] = dp[i][j - 1] + 10007 - dp[i - 1][j - 1];
else
dp[i][j] = (dp[i][j - 1] - dp[i - 1][j - 1]);
sum += dp[i][j] % 10007;
sum %= 10007;
+10007
이 조금은 뜬금없이 보일 수 있음두번째 풀이
첫번째 풀이에서 뺄셈의 방식이 아닌 덧셈의 방식으로 풀이를 진행해봐야할듯
#include <iostream>
#include <vector>
int n;
std::vector<std::vector<int> > dp;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
std::cin >> n;
dp.resize(n + 1, std::vector<int>(10, 1));
}
void solution()
{
long long sum;
sum = 10;
for (int i = 2; i <= n; i++)
{
dp[i][0] = sum;
for (int j = 1; j <= 9; j++)
{
if (dp[i][j - 1] < dp[i - 1][j - 1])
dp[i][j] = dp[i][j - 1] + 10007 - dp[i - 1][j - 1];
else
dp[i][j] = (dp[i][j - 1] - dp[i - 1][j - 1]);
sum += dp[i][j] % 10007;
sum %= 10007;
}
}
std::cout << sum;
}
int main(void)
{
input_setting();
input();
solution();
return (0);
}