백준 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)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
공부안하니까 3
계속 안하고싶어지노 아파서 누워있다가 일어났는데 ㄹㅇ 걍 백수가 내인생같음
-
빠른94니 94로 할게요 ㅋㅋ저도 조마조마했었는데.. 게시판 보면서 먼저 붙은 분들...
오 저 이거 풀어본 적 있는듯
모두 함께 백준합시다조와요~ 저도 컴공이라 곧 다시 시동 걸어야 겠어요
몇학번이신가요?
23이요!
백준 dp 문제는 확실히 규칙 찾는 센스가 필요한 문제가 많은 거 같아요! 그걸 응용한 게 게임 이론 중 일부인데, 문제들 중 ‘돌 게임’ 도 추천드립니다!
https://www.acmicpc.net/workbook/view/7836
이거 순서대로 풀려는 중입니다 ㅎㅎ
돌게임은 실5네요? 도전각