https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기
문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각
www.acmicpc.net
간단한 다이나믹 프로그래밍 문제라고 할수 있겠습니다.
사실 처음 할때 개념을 이해하기가 꽤 힘들었던 것 같았던 기억이 있습니다....
이번에 아이패드를 사면서 사용하면서 풀고 있는데 보면서 약간 이해를 도울 수 있었으면 좋겠네요
목표지점 n으로 가기 위해 정수 123만 사용할수 있기 때문에
4이상의 숫자들은 1칸 가고 목표지점에 가는 경우의 수 dp[n-1]
2칸 가고 목표지점에 가는 경우의 수 dp[n-2]
3칸 가고 목표지점에 가는 경우의 수 dp[n-3]
으로 이해하시면 편하지 않을까 생각합니다.
<필기>
<코드>
'알고리즘 문제풀이 > 다이나믹 프로그래밍' 카테고리의 다른 글
| 백준 11726 [C++] (0) | 2020.12.14 |
|---|---|
| 백준 7570 [C++] (0) | 2020.12.02 |
| 백준 12865 [C++] (0) | 2020.11.29 |
| 백준 1932 (0) | 2020.03.02 |
| 백준 2579 (0) | 2020.02.01 |