[백준/C] 10819 - 차이를 최대로

https://www.acmicpc.net/problem/10819

구현 과정

재귀함수를 이용하면 된다.

start == n 이면 주어진 배열의 끝까지 진행한 것이므로 현재 수열의 모든 원소의 차이의 합을 구하고, max보다 크면 max 값을 업데이트한다.

start 부터 n-1번째까지

1. 두 요소 바꿔보기
2. 다시 재귀함수 호출

을 반복한다. start == n 조건을 만족해서 리턴되었을 때는 바꿔본 두 요소를 원래 상태로 복구해준다.

void findMax(int *nums, int start, int n, int *max) {
    if (start == n) {
        int currentSum = 0;
        for (int i = 0; i < n - 1; i++)
            currentSum += abs(nums[i] - nums[i + 1]);

        if (currentSum > *max)
            *max = currentSum;
        return;
    }

    for (int i = start; i < n; i++) {
        swap(&nums[start], &nums[i]);
        findMax(nums, start + 1, n, max);
        swap(&nums[start], &nums[i]);
    }
}

작동 과정

주어진 배열이 [20, 1, 15, 8, 4, 10] 인 경우

• start = 0, max = 0 에서 시작
• swap(&nums\[0], &nums\[0]) -> findMax(start = 0 + 1) 호출
• swap(&nums\[1], &nums\[1]) -> findMax(start = 1 + 1) 호출
• swap(&nums\[2], &nums\[2]) -> findMax(start = 2 + 1) 호출
• findMax(start = 5 + 1) 호출하면 start == n 조건에 걸려 원소 차이의 합을 계산하고 max = 50으로 업데이트된다. 결국 첫 번째에서는 주어진 배열 그대로인 경우를 따져보는 것이다.
• return되면 findMax가 호출되는 아랫줄의 swap으로 돌아와 교환한 원소를 원상복귀 해준다.
• 교환 이후 for문의 i가 1 증가해 두 번째 단계에서는 i = 1 부터 시작하게 된다.
  

전체 코드

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void findMax(int *nums, int start, int n, int *max) {
    if (start == n) {
        int currentSum = 0;
        for (int i = 0; i < n - 1; i++)
            currentSum += abs(nums[i] - nums[i + 1]);

        if (currentSum > *max)
            *max = currentSum;
        return;
    }

    for (int i = start; i < n; i++) {
        swap(&nums[start], &nums[i]);
        findMax(nums, start + 1, n, max);
        swap(&nums[start], &nums[i]);
    }
}

int main() {
    int n;
    scanf("%d", &n);

    int *nums = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
        scanf("%d", &nums[i]);

    int max = 0;
    findMax(nums, 0, n, &max);

    printf("%d\n", max);
    free(nums);
    return 0;
}

값 교환해서 원본 변수를 변경하고 싶을 때는 꼭 포인터 사용하기!