무브

오르비

아톰

내 태그

내 태그 설정

입시
학습
생활
클럽
직업·취업
Epioptimus
Centurion

수능쎈츄 [1174003] · MS 2022 (수정됨) · 쪽지

2023-01-14 01:48:51
조회수 2,754

백준 9095번: 1, 2, 3 더하기(실 III)

게시글 주소: https://orbi.kr/00061312886

문제: https://www.acmicpc.net/problem/9095 


정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.


1+1+1+1

1+1+2

1+2+1

2+1+1

1+3

3+1


정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.












점화식을 dp[i]=dp[i-1]+dp[i-2]+dp[i-3]+6;으로 잘못 생각해서 맞왜틀 하고 다시보니

전 문제와 다르다는걸 깨닫고 고침




이건 반복문

이 문제는 n<=11이라는 아주 적은 숫자라 미리 테이블을 짜놨지만 담부터는 안 그럴 예정

#include <stdio.h>


int dp[12]={0,1,2,4,0};


int main()

{

    int i,n,T;

    

    for(i=4; i<=11; i++) dp[i]=dp[i-1]+dp[i-2]+dp[i-3];

    

    scanf("%d", &T);

    

    for(;T--;) scanf("%d",&n),printf("%d\n", dp[n]);

}



이건 재귀

#include <stdio.h>


int dp[12]={0,1,2,4,0};


int todo(int n)

{

    if(!dp[n]) dp[n]=todo(n-1)+todo(n-2)+todo(n-3);

    return dp[n];

}


int main()

{

    int i,n,T;

    

    scanf("%d", &T);

    

    for(;T--;) scanf("%d",&n),printf("%d\n", todo(n));

}

0 XDK (+0)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

수능쎈츄 [1174003]

쪽지 보내기

글쓰기
오르비 1380905번째 회원 가입
ddna
1,422,072 건의 게시물이
블록체인에 디지털 공증되었습니다.
901,751
497,321
22,267
574
159

댓글이 많은 글

2026 수능D - 267

오르비 플레이
오르비 RARE
오르비 과외시장
Move
our corporate site
Orbi Class
on-line classes
Atom
educational books & resources
Gae9
humor and fun

© 2000-2025 Move Inc.

orbisoptimus (v17-704e1f)