백준 17088번: 등차수열 반환

문제

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

17088번: 등차수열 변환

---

풀이

크기가 N인 수열 A = [A1, A2,..., AN]이 있을 때 각각의 수에 1을 더하거나 1을 빼는 연산을 최대 한 번씩만 사용해서 등차수열을 반환하는 연산 횟수의 최솟값을 구하는 문제입니다.

---

코드

C언어

먼저 n이 1이라면 무조건 등차수열이므로 0을 출력하고 exit(0)을 통해 프로그램을 종료합니다. 1이 아니라면 아래에서 등차수열을 만들어갑니다.

이때 등차수열 배열의 각 원소 간의 차이는 0번 인덱스의 원소(arr[0])와 1번 인덱스의 원소(arr[1])간의 차이와 같습니다. arr[0]과 arr[1]에도 연산을 사용할 수 있으므로 i와 j를 이용한 이중 for문을 사용했습니다. 이때 i는 arr[0]에서, j는 arr[1]에서 1을 더하거나 빼는 연산, 혹은 아무런 연산도 하지 않음을 정해줍니다. 연산 횟수를 나타내는 cnt를 0으로 초기화한 뒤에 아무런 연산도 하지 않을 경우(i가 0일 경우와 j가 0일 경우)를 제외하고 cnt에 1씩 더해줍니다. 연산을 마친 0번 인덱스의 원소를 a0, 연산을 마친 1번 인덱스의 원소를 a1이라고 했을 때 d는 이 둘의 차이를 의미하고 등차수열이라고 가정했을 때 k번 인덱스에 있어야 하는 원소를 의미하는 ak에 a1을 넣어줍니다.

k를 이용한 for문 안에서 ak에 d를 빼가며 arr[k]와 비교합니다. 같다면 연산할 필요가 없으므로 넘어가고 arr[k]와 ak의 차이가 1이라면 연산을 한 번 수행하면 되기 때문에 cnt에 1을 더해줍니다. 차이가 1보다 크다면 등차수열을 만들 수 없기 때문에 등차수열 제작 가능 여부를 확인하는 bool형 정수 tst에 0을 넣어주고 break로 j를 포함한 for문을 빠져나옵니다.

tst가 1이라면 등차수열을 만드는 것을 성공한 경우이므로 연산 횟수의 최솟값을 의미하는 min과 비교하며 더 작은 값을 구합니다.

모든 경우를 확인한 후에 min이 초기값(INT_MAX)과 다르다면 그 값을 출력하고, 초기값과 같다면 등차수열을 만들지 못한 것으로 -1을 출력합니다.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#define math_min(a, b) a < b ? a : b
main() {
	int n, min = INT_MAX;
	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	if (n == 1) {
		printf("0");
		exit(0);
	}
	for (int i = -1; i <= 1; i++) {
		for (int j = -1; j <= 1; j++) {
			int cnt = 0;
			if (i != 0) cnt++;
			if (j != 0) cnt++;
			int a0 = arr[0] + i, a1 = arr[1] + j;
			int d = a0 - a1, ak = a1, tst = 1;
			for (int k = 2; k < n; k++) {
				ak -= d;
				if (arr[k] == ak) continue;
				else if (abs(arr[k] - ak) == 1) cnt++;
				else {
					tst = !tst;
					break;
				}
			}
			if (tst) {
				min = math_min(min, cnt);
			}
		}
	}
	if (min == INT_MAX) {
		printf("-1");
	}
	else {
		printf("%d", min);
	}
}

자바

위의 C언어를 이용한 풀이와 방식은 비슷하지만 브루트포스가 아닌 dfs를 이용하였습니다.

위의 코드와 마찬가지로 먼저 n이 1이라면 무조건 등차수열이므로 0을 출력하고 exit(0)을 통해 프로그램을 종료합니다. 1이 아니라면 아래에서 등차수열을 만들어갑니다.

i와 j를 이용한 이중 for문으로 arr[0]와 arr[1]에 각각의 연산 후의 결과를 저장하고 등차수열에서 원소 간의 차이를 의미하는 전역 변수 d를 arr[0] - arr[1]로 지정합니다. 이때 위의 코드와 마찬가지로 i는 arr[0]에서, j는 arr[1]에서 1을 더하거나 빼는 연산, 혹은 아무런 연산도 하지 않음을 정해줍니다. 연산 횟수를 나타내는 cnt를 0으로 초기화한 뒤에 아무런 연산도 하지 않을 경우(i가 0일 경우와 j가 0일 경우)를 제외하고 cnt에 1씩 더해줍니다. arr[2]부터 arr[n - 1] 사이를 테스트하기 위해 dfs(1, cnt)를 실행합니다.dfs 함수 내부에서 정수 gap은 dpth번 인덱스의 원소와 그다음 원소의 차이를 의미합니다. 이때 gap이 d와 같다면 아무런 연산을 실행하지 않으므로 cnt를, gap과 d의 차이가 1이라면 그 차이만큼 arr[dpth + 1]에 더해준 뒤에 cnt에 1을 더한 값을 함수의 매개변수로 사용하며 재귀적으로 실행합니다. 차이가 1보다 크다면 연산을 통해 등차수열을 만들 수 없으므로 함수를 종료합니다. 다음 테스트를 위해 바꾼 arr의 원소들은 모두 원래대로 되돌려놓습니다.dpth가 배열의 끝인 n - 1이 됐다면 등차수열을 만드는 것을 성공한 경우이므로 연산 횟수의 최솟값을 의미하는 min과 비교하며 더 작은 값을 구합니다. 함수가 종료됐다면 다음 테스트를 위해 arr[0]과 arr[1]를 원래대로 되돌려놓습니다.

모든 경우를 확인한 후에 min이 초기값(INT_MAX)과 다르다면 그 값을 출력하고, 초기값과 같다면 등차수열을 만들지 못한 것으로 -1을 출력합니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int n, d, min;
    static int[] arr;

    public static void dfs(int dpth, int cnt) {
        if (dpth == n - 1) {
            min = Math.min(min, cnt);
            return;
        }
        int gap = arr[dpth] - arr[dpth + 1];
        if (gap == d) {
            dfs(dpth + 1, cnt);
        } else if (Math.abs(gap - d) == 1) {
            arr[dpth + 1] += (gap - d);
            dfs(dpth + 1, cnt + 1);
            arr[dpth + 1] -= (gap - d);
        }
        return;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        if (n == 1) {
            System.out.println(0);
            System.exit(0);
        }
        min = Integer.MAX_VALUE;
        for (int i = -1; i <= 1; i++) {
            arr[0] += i;
            for (int j = -1; j <= 1; j++) {
                int cnt = 0;
                arr[1] += j;
                d = arr[0] - arr[1];
                if (i != 0) cnt++;
                if (j != 0) cnt++;
                dfs(1, cnt);
                arr[1] -= j;
            }
            arr[0] -= i;
        }
        if (min == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(min);
        }
    }
}

 

처음에 dfs를 이용하여 이 문제를 풀 때 함수를 만들었습니다. 이렇게 만들었을 때의 문제점은 중간에 등차수열을 만들 수 없다는 사실이 확실해져도 배열의 끝까지 이동한 후에 for문을 이용하여 테스트하기 때문에 모든 경우의 수를 확인한다는 것입니다.

public static void dfs(int dpth, int cnt) {
    if (dpth == n) {
        int gap = arr[0] - arr[1];
        for (int i = 1; i < n - 1; i++) {
            if (arr[i] - arr[i + 1] != gap) {
                return;
            }
        }
        min = Math.min(min, cnt);
        return;
    }
    dfs(dpth + 1, cnt);
    arr[dpth]++;
    dfs(dpth + 1, cnt + 1);
    arr[dpth] -= 2;
    dfs(dpth + 1, cnt + 1);
    arr[dpth]++;
}

---

결론

같은 문제를 풀더라도 이 문제처럼 해결방법은 여러 가지가 있다는 것을 알게 되었습니다. 앞으로는 제 방식대로 문제를 풀더라도 푼 이후에 다른 사람들은 어떻게 풀었는지 확인해가며 어떤 코드가 더 깔끔하고 이해하기 쉬운지 확인하는 습관을 만들어야겠습니다.