-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
85번 수식만들기 질문드립니다.
20.03.02 21:06 작성 조회수 141
0
#include <stdio.h>
int a[30],cal[30],n,max=-2147000000,min=2147000000;
int Calc(int index,int a, int b)
{
switch(index)
{
case 1:
return a+b;
break;
case 2:
return a-b;
break;
case 3:
return a*b;
break;
case 4:
return a/b;
break;
}
}
void DFS(int L, int sum)
{
if(L==n+1){
if(max<sum) max=sum;
if(min>sum) min=sum;
}
else{
for(int j=1; j<=4; j++){
if(cal[j]!=0){
DFS(L+1,Calc(j,a[L],sum));
cal[j]--;
}
}
}
}
int main(void){
freopen("input.txt","rt",stdin);
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
for(int i=1; i<=4; i++){
scanf("%d",&cal[i]);
}
DFS(1,0);
printf("%d\n%d\n",max,min);
}
위에데로 해보니 출력결과가 64 16 이렇게 나옵니다.(정답은 64 23) 16이 아마 5+3+8해서 나온것 같은데.
분명 위에 DFS함수 보시면 cal[j]-- 로 빼주고 있는데 왜 덧셈연산이 중복되서 두번 나오는걸까요?..
어디가 잘못됬는지 잘모르겠어서 질문드립니다.
답변을 작성해보세요.
1
김태원
지식공유자2020.03.02
#include <stdio.h>
int a[30],cal[30],n,max=-2147000000,min=2147000000;
int Calc(int index, int a, int b)
{
switch(index)
{
case 1:
return a+b;
break;
case 2:
return a-b;
break;
case 3:
return a*b;
break;
case 4:
return a/b;
break;
}
}
void DFS(int L, int sum)
{
if(L==n+1){
if(max<sum) max=sum;
if(min>sum) min=sum;
}
else{
for(int j=1; j<=4; j++){
if(cal[j]!=0){
cal[j]--; //재귀가 넘어가기 전에 빼줘야 합니다.
DFS(L+1, Calc(j, sum, a[L])); //sum이 앞에, a[L]이 뒤에 인자가 되어야 합니다. 빼기와 나누기에서는 중요합니다.
cal[j]++; //다시 되돌아 오면 더해서 다시 사용하게끔 해줍니다.
}
}
}
}
int main(void){
freopen("input.txt","rt",stdin);
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
for(int i=1; i<=4; i++){
scanf("%d",&cal[i]);
}
DFS(2, a[1]); //레벨은 2부터 시작하고 첫 번째 숫자를 인자로 넘겨야 합니다. 연산자는 첫 번째 숫자와 두 번째 숫자 사이에서 처음 시작합니다.
printf("%d\n%d\n",max,min);
}
본인이 짠 코드가 이상할 경우 강의 영상에서 설명하는 코드를 완벽하게 이해하고 내가 짠 코드를 리뷰하며 잘 못된 점을 찾는 방식으로 공부하면 실력이 급상승 할 겁니다. 아무리 해도 모르겠을 경우에는 저에게 질문하시구요^^
답변 1