C언어 백준 - 15658, 10819 풀이

c언어로 백트래킹 문제들을 풀어보면 알고리즘 문제나 42문제 푸는데 도움이 될거 같아서
풀어보고 있다!

그 중 대표적인 문제들을 풀어봤고 여기 나름대로 풀이해서 적어봤다

연산자 끼워넣기(2)

연산자 끼워넣기(2) Link!

문제 풀이

이 문제의 핵심은 다양한 연산자를 이용해서 어떻게 최솟값과 최댓값을 구할지를 고민하는 문제다!
차고로 연산자 우선순위가 없이 무조건 앞부터 계산을 진행한다!

예시)
1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6

문제 해석

이 문제를 보고 백트래킹으로 마지막 숫자까지 계산,
즉 N-1까지 연산자를 넣고 MAX, MIN 값에 비교해 넣어주고자 했다

코딩

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
int n;
int arr[12];
int min = 1000000001;
int max = -1000000001;

void dfs(int depth, int sum, int plus, int minus, int multi, int div) {
	if(depth == n-1) {
    	if(sum < min) { min = sum; }
        if(sum > max ) { max = sum; }
        
        return;
    }
    
    if(plus > 0) dfs(depth+1, sum + arr[depth+1], plus-1, minus, multi, div);
    if(minus > 0) dfs(depth+1, sum - arr[depth+1], plus, minus-1, multi, div);
    if(multi > 0) dfs(depth+1, sum * arr[depth+1], plus, minus, multi-1, div);
    if(div > 0) dfs(depth+1, sum / arr[depth+1], plus, minus, multi, div-1);
	    
}


int main() {
	scanf("%d", &n);
    for(int i =0; i<n; i++) { scanf("%d", &arr[i]); }
    int plus,minus,multi, div;
    scanf("%d",&plus);
    scanf("%d",&minus);
    scanf("%d",&multi);
    scanf("%d",&div);
    
    dfs(0,arr[0],plus,minus, multi, div);
    printf("%d", max);
    printf("%d", min);

	return 0;
}

차이를 최대로

차이를 최대로 Link!

문제 풀이

앞에 문제는 연산자를 조합해서 결과를 찾아봤다면
이 문제는 숫자들의 순서를 바꿔서 최댓값을 찾으면 된다!

문제 해석

문제의 핵심은 2가지로 볼 수 있다!!

1. 모든 숫자들의 순열을 구할 수 있는가!
2. 백트래킹으로 마지막 N까지 반복을 어떻게 시킬 것인가!

여기서 순열을 구하는 방법으로는 visited라는 bool 배열을 사용해서
방문 안했다면 아직 안 사용한 숫자로 판단해 추가하는 방식으로 순열을 만들었다

코딩

#include<stdio.h>
#include<stdbool.h>
int n,result = -1000;
int arr[9];
int rep[9];
bool visited[9];

void dfs(int depth) {
	if(depth == n) {
    	int subResult = 0;
        for(int i = 0; i<n-1; i++) {
            if(subResult <0) subResult *= -1;
            subResult += (rep[i] - rep[i+1]);
        }
        if(result < subResult) {
        	result = subResult;
        }
        return;
    }
    
    for(int i=0; i<n; i++) {
    	if(!visited[i]) {
        	visited[i] = true;
            rep[depth] = arr[i];
            dfs(depth+1);
            visited[i] = false;
        }
    }
}


int main() {
	scanf("%d",&n);
    for(int i =0; i<n; i++) {
    	scanf("%d",&arr[i]);
    }
    dfs(0);
    
    printf("%d\n", result);

	return 0;
}