[boj] (s3) 9095 1,2,3 더하기
✅ DP
문제
1. 문제 접근 및 해결 로직
구성 숫자가 같아도 순서가 다른 것은 다른 조합으로 친다.
따라서 을 정수 을 1,2,3의 합으로 나타내는 방법의 수라고 하고
몇가지를 구해보면
{1}
{1,1}
{2}
{1,1,1}
{1,2}
{2,1}
{3}
{1,1,1,1}
{1,2,1}
{2,1,1}
{1,1,2}
{3,1}
{1,3}
{2,2}
여기서 다음과 같은 규칙을 발견할 수 있다.
따라서 점화식은
이다.
의사코드
- 정의
: 정수 을 1,2,3의 합으로 나타내는 방법의 수- 구하는 답
- 초기값
- 점화식
2. 코드
3. 시간 복잡도 분석
경우의 수를 모두 구하므로
4. 문제에서 중요한 부분
DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항
Author And Source
이 문제에 관하여([boj] (s3) 9095 1,2,3 더하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@peanut_/boj-s3-9095-123-더하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)