poj-1664 [사과 넣기]
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 30957
Accepted: 19540
Description
같은 사과 M개를 같은 접시 N개에 넣고 어떤 접시는 비워두고 놓지 않도록 허락하는데, 모두 몇 가지의 다른 분법이 있느냐고 물었다.(K로 표시) 5, 1, 1과 1, 5, 1은 같은 분법이다.
Input
첫 번째 줄은 테스트 데이터의 수량 t(0 <=t <=20)입니다.다음 행에는 공백으로 구분된 두 개의 정수 M과 N이 있습니다.1<=M,N<=10.
Output
입력한 각 데이터 그룹 M과 N에 대해 한 줄로 해당하는 K를 출력합니다.
Sample Input
1
7 3
Sample Output
8
이런 문제에 대해 만약에 수학 사상에 따라 조금씩 배열하고 싶다면 정말 쉽지 않다. 인터넷상에서 모두 귀환으로 하는 것을 보면 사실 나는 귀환을 잘하지 못한다. 이 문제를 읽은 후에 나는 할 줄 알지만 귀환이 어떻게 세밀하게 연산하는지 모르겠다. 나도 대략적인 것만 알 수 있다. 그는 사실 적은 것에서 많은 것으로, 귀환은 큰 것에서 작은 것으로, 작은 것에서 작은 것까지 작은 것에서 큰 데이터로 밀고 있다.우리는 매우 큰 데이터의 답을 알 수 없기 때문에 데이터가 적을 때의 답을 알 수 있다. (필자의 수다를 싫어하지 마라* *) 이 문제에 따라 우리는 m개의 사과를 분석한다. n개의 접시 dp(m, n)는 m개의 사과를 n개의 접시에 넣는 방안 수 1, 애플 m=1, (n>=1)dp(1, n)=1을 대표한다.2, n=1시, dp(m, 1)=1;3. n>=m일 때 dp(m,n)==dp(m,m);4. nm개의 사과를 n개의 접시에 놓으면 n개의 접시마다 사과와 dp(m, n-1)가 있다.그리고 이곳의 dp(m, n-1)는 다음 귀환에 들어갈 것이다. 계속 이러기 때문에 귀환은 공간을 낭비하는 복잡도와 시간 복잡도가 비교적 높다. n<=10을 발견할 수 있다.이유가 여기에 있는 것 같아요.
#include
int dp(int m,int n)
{
if(m==1||n==1||n==0)
return 1;
else
{
if(n>m)
return dp(m,m);
else
return dp(m-n,n)+dp(m,n-1);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&m,&n);
printf("%d
",dp(m,n));
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
