알고리즘
백준 10844: 쉬운 계단 수(DP)
Aye Bye Eye
2019. 8. 19. 16:04
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include <iostream> unsigned int dp[101][10]; int main() { int N = 0; std::cin >> N; for (int i = 1; i <= 9; ++i) dp[1][i] = 1; for (int i = 2; i <= N; ++i) for (int j = 0; j < 10; ++j) { if (j == 0) dp[i][j] = dp[i - 1][j + 1]; else if (j == 9) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000; } unsigned long long ans = 0; for (int i = 0; i < 10; ++i) ans += dp[N][i]; std::cout << ans % 1000000000; return 0; } | cs |
십억을 중간과정에서 나머지연산하면 오버플로는 막겠지만 값이 변하지 않나..
하... 모르겠다...
그냥 전체적으로 조졌다... 왜 일케 하는지는 알겠는데 내가 직접 로직을 세우지도 못했고... 아직도 나머지연산은 이해가 안대고... DP빡고수라고 자화자찬 하자마자 개뚜드려맞았다...