문제접근
1.
첫번째 풀이
•
DP를 2차원으로 두고 DP[수의 길이][첫자리숫자]를 나타내었다
•
DP에는 그 상태에서 가능한 오르막 수의 개수를 나타낸다
•
위처럼 DP[][0]에는 전 행의 총합이 들어가게 되고, DP[][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);
}
C++
복사
→라고 생각했는데 분기를 통해서 해결할 수 있었음(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;
C++
복사
•
이 구문에서 보면 +10007 이 조금은 뜬금없이 보일 수 있음
•
현재 저 분기가 나온 이유는 예를들어 (10008 % 10007) - (10006 % 10007)의 경우 음수가 나오기 때문에 이런 경우 10008에 + 10007을 통하여 먼저 음수가 나올 상황을 없애주고 그 후에 % 10007을 해주면 원래 결과와 똑같기 때문
2.
두번째 풀이
•
첫번째 풀이에서 뺄셈의 방식이 아닌 덧셈의 방식으로 풀이를 진행해봐야할듯
놓쳤던 부분
•
자료형 범위 초과로 인한 오버플로우로 잘못된 값을 출력하는 것에 대해서 인지를 하지 못했다
•
dp[i][j]
코드
2160 KB
0 ms
#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);
}
C++
복사
