[백준 17088] 등차수열 변환, C++

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

17088번: 등차수열 변환

 본 문제는 주어진 수열을 등차수열로 변환하는 문제로 각각의 수에 연산을 최대 한 번 적용할 수 있고, 연산은 1을 더하거나 빼는 것만 가능하다. 주어진 수열을 등차수열로 변환하기 위해 필요한 연산 횟수의 최솟값을 구하는 문제다. 조건 중에 등차수열로 변환시킬 수 없다면 -1을 출력한다.

처음으로 생각난 코드는 brute force였다. 모든 경우를 다 만들고, 등차수열 여부를 검사하는 방법을 선택했다.

1. 0번 index 부터 시작
2. 1을 더하는 경우
3. 1을 빼는 경우
4. 연산을 안하는 경우
5. 등차수열 확인

 

brute force

#include <cstdio>
#include <vector>
 
using namespace std;
 
int n;
int ans = -1;
 
vector<int> v;
void cal(int index, vector<int> &u, int cnt) {
    if (index == v.size()) {
        // 등차수열 확인
        int chk = u[1] - u[0];
        for (int i = 2; i < v.size(); i++) {
            if (u[i] - u[i-1] != chk) return;
        }
        if (ans == -1 || ans > cnt) ans = cnt;
        return;
    }
    // 1을 더하는 경우
    u.push_back(v[index]+1);
    cal(index+1, u, cnt+1);
    u.pop_back();
 
    // 1을 빼는 경우
    u.push_back(v[index]-1);
    cal(index+1, u, cnt+1);
    u.pop_back();
 
    // 연산을 안하는 경우
    u.push_back(v[index]);
    cal(index+1, u, cnt);
    u.pop_back();
 
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int tmp;
        scanf("%d", &tmp);
        v.push_back(tmp);
    }
    vector<int> u;
    // 0번 index 부터 시작
    cal(0, u, 0);
    printf("%d\n", ans);
}

그러나 시간초과를 받았다. 모든 경우의 수 중, 등차 수열이 될 가능성이 없는 연산은 할 필요가 없다. 즉, back tracking을 이용해야 한다.

초기 등차수열의 크기는 9가지 경우밖에 없다. 9가지 경우 중에서 등차 수열이 되는 모든 경우의 수를 찾자

1. 초기 등차수열의 크기 정하기
2. 연산을 안하는 경우
3. 1을 더하는 경우
4. 1을 빼는 경우
5. 등차 수열이 아닌 경우

어라? 이번엔 틀렸다. 왜 틀렸을까?

입력의 크기를 보면 1부터 시작이다. 그렇기 때문에 등차수열의 크기가 1인 경우를 예외처리한다.

 

back tracking

#include <cstdio>
#include <vector>
 
using namespace std;
 
int n;
int ans = -1;
 
vector<int> v;
// x < y
void cal(int x, int y, int index, int cnt) {
    if (index == v.size()) {
        if (ans == -1 || ans > cnt) ans = cnt;
        return;
    }
    int tmp = y - x;
    // 연산을 안하는 경우
    if (v[index] - y == tmp) cal(y, v[index], index+1, cnt);
    // 1을 더하는 경우
    else if (v[index]+1 - y == tmp) cal(y, v[index]+1, index+1, cnt+1);
    // 1을 빼는 경우
    else if (v[index]-1 - y == tmp) cal(y, v[index]-1, index+1, cnt+1);
    // 등차수열이 아닌 경우
    else return;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int tmp;
        scanf("%d", &tmp);
        v.push_back(tmp);
    }
    // 등차수열의 크기가 1인 경우
    if (n == 1) {
        printf("0\n");
        return 0;
    }
    vector<int> u;
    
    // 초기 등차수열의 크기 정하기
    cal(v[0], v[1], 2, 0);
    cal(v[0], v[1]+1, 2, 1);
    cal(v[0], v[1]-1, 2, 1);
 
    cal(v[0]+1, v[1], 2, 1);
    cal(v[0]+1, v[1]+1, 2, 2);
    cal(v[0]+1, v[1]-1, 2, 2);
 
    cal(v[0]-1, v[1], 2, 1);
    cal(v[0]-1, v[1]+1, 2, 2);
    cal(v[0]-1, v[1]-1, 2, 2);
    
    printf("%d\n", ans);
}