🤍 전 강의 25% 할인 중 🤍

2024년 상반기를 돌아보고 하반기에도 함께 성장해요!
인프런이 준비한 25% 할인 받으러 가기 >>

  • 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

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

답변을 작성해보세요.

1

#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);
}

본인이 짠 코드가 이상할 경우 강의 영상에서 설명하는 코드를 완벽하게 이해하고 내가 짠 코드를 리뷰하며 잘 못된 점을 찾는 방식으로 공부하면 실력이 급상승 할 겁니다. 아무리 해도 모르겠을 경우에는 저에게 질문하시구요^^

채널톡 아이콘