코후닝

알고리즘 분류 : DPhttps://www.acmicpc.net/problem/15989   정수 n을 1, 2, 3의 합으로 표현하는 방법의 수를 구하는 문제이다.각각의 경우에서 숫자는 1, 2, 3을 한 번에 하나씩만 더해 나가며 만들 수 있다.여기서 주의할 점은 순서만 다르고 합을 이루고 있는 요소가 같은 경우는 카운트에서 제외해야한다.  일단 n=1, 2, 3일 때를 살펴보자. n=1 일 때,1=1경우의 수는 1가지이다. n=2일 때2=1+12=2경우의 수는 2가지이다. n=3일 때,3=1+1+13=1+23=3경우의 수는 3가지이다. 얼핏 보면, n=3일 때를 보면 n=2일 때에서 +1을 붙인 경우, n=1일 때에서 +2을 붙인 경우, n=0일 때에서 +3을 붙인 경우가 보이는 것을 알 수 있다...