[C/C++ 백준 15988번] 1, 2, 3 더하기 3 (Silver 2)
www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net #include #include using namespace std; int dp[1000000]; int main(void){ int T, a; scanf("%d", &T); dp[1] = 1; dp[2] = 2; dp[3] = 4; for(int i=4; i
[C/C++ 백준 15990번] 1, 2, 3 더하기 5 (Silver 3)
www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 수의 순서가 달라져도 다른 것으로 치지만, 연속한 두 수는 카운트하지 않는다. dp[i][j]를 정수 i의 끝이 j로 끝나는 가짓수라고 하고 문제를 해결하자. 즉 dp[i][1]의 경우 1로 끝나는 i를 합으로 나타내는 경우의 가짓수 이므로, dp[i-1][2] + dp[i-1][3]의 합이다. #include #include using namespace std; int main(void){ int T, dp[100001][4], a; for(int i=1; i
