목록9095 (1)

JINWOOJUNG

[ DP - 9095 ] 1, 2, 3 더하기

접근법 직접 해 보는 것이 DP문제에서 규칙을 찾는 가장 쉬운 방법인 것 같다. 1 표현 1 2 표현 1+1 2 3 표현 1+1+1 1+2 2+1 3 1,2,3은 각각 1,2,4가지로 표현 가능하다. 4를 1,2,3의 합으로 나타내보자. 1+1+1+1 1+1+2 1+2+1 1+3 2+2 2+1+1 3+1 총 7가지인데, 처음이 1일 때 나머지 3을 나타낼 수 있는 가지수는 위에서 구한 4가지, 처음이 2일 때 나머지 2를 나타낼 수 있는 가지수는 2가지 그리고 처음이 1이면 1가지 이다. 따라서 DP[4] = DP[4-1] + DP[4-2] + DP[4-3] 으로 표현 가능하다. 이제 구현해보자. 정답 #include #include using namespace std; int32_t DP[12]; in..
백준 2024. 3. 29. 13:06
이전 Prev 1 Next 다음