반응형
https://www.acmicpc.net/problem/15988
15988번: 1, 2, 3 더하기 3
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
www.acmicpc.net
일반적인 DP문제다.( https://solution-is-here.tistory.com/16?category=979031 )
(C언어)DP Dynamic Programming 설명
다이나믹 프로그래밍은 취업을 할려면 필수로 배워야 하는 함수 같았다. 다이나믹 프로그래밍을 쉽게 말하자면 계산횟수를 줄여주는 함수다. 아직 C언어를 제대로 배우지 못해 코딩을 많이 안
solution-is-here.tistory.com
그러나 정답률이 35%인 데는 이유가 있다.
자료형을 무시하고 지나친 사람들에게 경각심을 주는 문제 같다.
코드를 보며 설명하겠다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <stdio.h>
#include <stdlib.h>
long long dp[1000000];
long long dynamic(int x)
{
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int a = 4; a <= 1000000; a++)
{
dp[a] = (dp[a - 1] + dp[a - 2] + dp[a - 3]) % 1000000009;
}
return dp[x];
}
|
cs |
1,2,3 더하기 시리즈를 푼 사람들이면 정수를 1,2,3의 합으로 나타내는식을 알것이다.
모르는 사람을 위해 한번 더 설명하자면, 4의 방법의 수를 구하려면 1,2,3의 방법의 수를 더하는 것이다.
6을 구하려면 4,=3,4,5의 방법의 수를 더하는 것이다.
dp[a] = (dp[a - 1] + dp[a - 2] + dp[a - 3])
그리고 중요! 1000000009로 나눈 나머지를 구하는 식을 return구문이 아닌 반복문 안에 넣어야 한다.
그 이유는 return구문에 넣으면 반복문 안의 dp[a]의 값이 1000000009가 넘어도 넘어가서
return구문에서 나머지 값을 구하기 때문에 값이 달라진다.
*말이 이해가 안되시는 분은 댓글을 남겨주시면 더 자세히 알려드리겠습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int main() {
int nums;
scanf("%d", &nums);
for (int a = 0; a < nums; a++)
{
int number;
scanf("%d", &number);
long long result = dynamic(number);
printf("%d\n", result);
}
return 0;
}
|
cs |
그 후, 횟수를 정하는 변수를 입력받은 뒤, 반복문을 만들어서 출력하면 된다.
Full Code
|
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
27
28
|
#include <stdio.h>
#include <stdlib.h>
long long dp[1000000];
long long dynamic(int x)
{
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int a = 4; a <= 1000000; a++)
{
dp[a] = (dp[a - 1] + dp[a - 2] + dp[a - 3]) % 1000000009;
}
return dp[x];
}
int main() {
int nums;
scanf("%d", &nums);
for (int a = 0; a < nums; a++)
{
int number;
scanf("%d", &number);
long long result = dynamic(number);
printf("%d\n", result);
}
return 0;
}
|
cs |
반응형