#include <cstdio>
int arr[1005]={};
int f(int n)
{
if(arr[n]!=0)
{
return arr[n];
}
if(n==1)
{
return 1;
}
if(n==2)
{
return 2;
}
arr[n]=f(n-1)+f(n-2);
return arr[n];
}
int main(){
int n;
scanf("%d",&n);
printf("%d",f(n)%10007);
return 0;
}
이 코드가 틀렸다고 뜨네요.
혹시 어디서 틀렸는지 반례와 답정도만 알려주실 수 있을까요?ㅠㅠ
백준 11726번 문제는 입력값 n이 주어졌을 때 2xn 직사각형을 채우는 방법의 수를 구하는 문제이므로 if문만을 사용하는 것이 아니라 동적으로 계산하기 위해 for와 같은 루프문이 필요합니다.
예를 들어, n이 3일 경우에는 2x3 직사각형을 채우는 방법의 수를 구해야 합니다.
이 경우에는 다음과 그림과 같이 총 3가지의 방법이 있습니다.
즉, 다음과 같이 나타낼 수 있습니다.
이것을 도식화하면 다음과 같은 그림이 될 수 있습니다.
결과적으로 아래와 같이 코드를 만들 수 있습니다.
#include <cstdio> const int MAX = 1005; int arr[MAX]={}; int f(int n) { if(n <= 1) return 1; // 예외 처리 if(arr[n]!=0) { return arr[n]; } arr[n] = (f(n-1) + f(n-2)) % 10007; return arr[n]; } int main(){ int n; scanf("%d",&n); printf("%d",f(n)); return 0; }즉, arr 배열에 이미 계산된 결과가 있는 경우 그 값을 반환하고, 그렇지 않은 경우 f(n-1)과 f(n-2)의 값을 더해 arr[n]에 저장한 후 반환합니다.
문제 상에 10007로 나눈 나머지를 출력하라고 하였으므로 구한 값에 10007을 나눈 나머지를 반환합니다.