Notice
Recent Posts
Recent Comments
tony9402
[백준 15989] 1,2,3 더하기 4 본문
반응형
문제 : 1,2,3 더하기 4
문제 유형 : 다이나믹 프로그래밍
이 문제는 1,2,3 더하기로 표현하는 것들 중에서 더하기 순서를 바꿨을때랑 같은 것을 한 종류로 보는 문제이다. 4를 가지로 예를 들어보자.
4를 1,2,3더하기로 표현해보면
3+1
2+2
1+3
2+1+1
1+2+1
1+1+2
1+1+1+1
이렇게 7가지가 있는데 더하기 순서를 바꾸면 같아지는것을 묶어보자.
3+1 (1+3)
2+2
2+1+1 (1+2+1, 1+1+2)
1+1+1+1
이렇게 4가지가 있다. 이것을 어떻게 수식으로 표현할까?
1,2,3 더하기 시리즈 문제는 모두 다이나믹 프로그래밍으로 풀 수 있다. 이를 재귀적으로 생각해보면 점화식이 보인다.
한 종류로 만들 때, 여러가지 순서 중 비오름차순으로 짜면 된다.
4를 가지고 예를 들어보자.
4에서 1,2,3을 빼면 모두 양수 이므로 아래와 같이 표현 할 수 있다.
3+□
2+□
1+□
그 다음에 □에는 뭐가 올 수 있을까?
바로 앞에서 사용한 숫자보다 작거나 같은 수가 오면 된다.
3+1
2+2
2+1+□
1+1+□
대충 하는 방법은 알겠지만 이를 가지고 어떻게 점화식을 세울지 안보인다. 그래서 난 표를 활용해봤다.
(핸드폰으로 표 그리는게 없네.....)
1 2 3
1 1 0 0
2 1 1 0
3 1 1 1
4 ? ? ?
(세로축을 i, 가로축을 j로 하자)
표를 그리면 이런식으로 그릴 수 있다. 가로축은 더하기에서 사용할 1 2 3, 세로축에 있는 건 n이다. n의 값이 1 2 3일땐 금방 구할 수 있으니 초기값으로 깔아놓고 보자.
n==4일때 1로 시작하는 더하기는 몇개일까?
문제 유형 : 다이나믹 프로그래밍
이 문제는 1,2,3 더하기로 표현하는 것들 중에서 더하기 순서를 바꿨을때랑 같은 것을 한 종류로 보는 문제이다. 4를 가지로 예를 들어보자.
4를 1,2,3더하기로 표현해보면
3+1
2+2
1+3
2+1+1
1+2+1
1+1+2
1+1+1+1
이렇게 7가지가 있는데 더하기 순서를 바꾸면 같아지는것을 묶어보자.
3+1 (1+3)
2+2
2+1+1 (1+2+1, 1+1+2)
1+1+1+1
이렇게 4가지가 있다. 이것을 어떻게 수식으로 표현할까?
1,2,3 더하기 시리즈 문제는 모두 다이나믹 프로그래밍으로 풀 수 있다. 이를 재귀적으로 생각해보면 점화식이 보인다.
한 종류로 만들 때, 여러가지 순서 중 비오름차순으로 짜면 된다.
4를 가지고 예를 들어보자.
4에서 1,2,3을 빼면 모두 양수 이므로 아래와 같이 표현 할 수 있다.
3+□
2+□
1+□
그 다음에 □에는 뭐가 올 수 있을까?
바로 앞에서 사용한 숫자보다 작거나 같은 수가 오면 된다.
3+1
2+2
2+1+□
1+1+□
대충 하는 방법은 알겠지만 이를 가지고 어떻게 점화식을 세울지 안보인다. 그래서 난 표를 활용해봤다.
(핸드폰으로 표 그리는게 없네.....)
1 2 3
1 1 0 0
2 1 1 0
3 1 1 1
4 ? ? ?
(세로축을 i, 가로축을 j로 하자)
표를 그리면 이런식으로 그릴 수 있다. 가로축은 더하기에서 사용할 1 2 3, 세로축에 있는 건 n이다. n의 값이 1 2 3일땐 금방 구할 수 있으니 초기값으로 깔아놓고 보자.
n==4일때 1로 시작하는 더하기는 몇개일까?
딱 하나밖에 없다. 1+1+1+1..
그럼 2로 시작하는 더하기는 몇개일까?
4에서 2를 빼보자. 그럼 2이다. 4에서 2를 뺐으니 2 이하로 된 수를 가지고 2를 만드는 갯수는 몇개일까?
4에서 2를 빼보자. 그럼 2이다. 4에서 2를 뺐으니 2 이하로 된 수를 가지고 2를 만드는 갯수는 몇개일까?
바로 n==2(i==2)일때 j가 1,2일때 값을 더하면 된다.
즉 1+1 =2(DP[2][1]+DP[2][2])개이다.
실제로도 직접 계산해보면 같다는걸 알 수 있다.
실제로도 직접 계산해보면 같다는걸 알 수 있다.
이제 4에서 3을 빼보자. 그럼 1이다. 위랑 마찬가지로 1을 1이하로 된 수를 가지고 만들 수 있는 갯수는 1개이다. 즉 DP[1][1]이다.
핸드폰으로 작성해서 그런지 생각나는 대로 쓰느라 제대로 쓰고 있는지 잘 모르겠다.
아무튼, 위의 방법을 가지고 점화식을 세워보자.
i에서 3을 뺐을땐 DP[i][3]=DP[i-3][1]+DP[i-3][2]+DP[i-3][3]
DP[i][2]=DP[i-2][1]+DP[i-2][2]
DP[i][1]=DP[i-1][1]
아무튼, 위의 방법을 가지고 점화식을 세워보자.
i에서 3을 뺐을땐 DP[i][3]=DP[i-3][1]+DP[i-3][2]+DP[i-3][3]
DP[i][2]=DP[i-2][1]+DP[i-2][2]
DP[i][1]=DP[i-1][1]
이를 하나의 식으로 쓰면 아래와 같다.
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include<iostream> using namespace std; typedef long long ll; int dp[10001][4]; int solve(int n, int k) { if (dp[n][k])return dp[n][k]; for (int i = 4; i <= n; i++) { for (int j = 1; j <= 3; j++) { int sum = 0; if (j == 1) { dp[i][j] = 1; continue; } for (int m = 1; m <= j; m++) { sum += dp[i - j][m]; } dp[i][j] = sum; } } return dp[n][k]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin >> T; dp[1][1] = dp[2][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1; for (; T--;) { int input; cin >> input; solve(input, 3); cout << dp[input][1] + dp[input][2] + dp[input][3] << '\n'; } return 0; } | cs |
반응형
'알고리즘 > Baekjoon Online Judge' 카테고리의 다른 글
[백준 15991] 1,2,3 더하기 6 (0) | 2018.11.24 |
---|---|
[백준 15990] 1,2,3 더하기 5 (0) | 2018.11.22 |
[백준 12101] 1,2,3 더하기 2 (0) | 2018.11.07 |
[백준 9095] 1, 2, 3 더하기 (0) | 2018.11.07 |
[백준 1806] 부분합 (0) | 2018.10.20 |
Comments