17088 c++ - 등차수열 변환

17088 c++ 등차수열 변환.

dfs로 풀었는데, 복사생성자를 인수로 받아서, 메모리 초과가 났다. dfs에서는 꼭 조심해줘야 하는 것을 다시 깨달았습니다.
그래서 고쳐서 레퍼런스로 제출했는데, 시간초과가 났습니다. 

수열의 길이가 10,000까지 될 수 있어서 각 항목에 대해 3가지 선택지를 가지므로, 완전 탐색하는 경우의 수는 (3^n) = 3^100000이 되는 것을 깨달았습니다. 그래서 수열로 접근하여 풀었습니다.

dfs로 푼 코드

/* ************************************************************************** */
/*                                                                            */
/*                                                      :::    :::    :::     */
/*   Problem Number: 17088                             :+:    :+:      :+:    */
/*                                                    +:+    +:+        +:+   */
/*   By: chanhihi <boj.kr/u/chanhihi>                +#+    +#+          +#+  */
/*                                                  +#+      +#+        +#+   */
/*   https://boj.kr/17088                          #+#        #+#      #+#    */
/*   Solved: 2024/10/16 19:16:17 by chanhihi      ###          ###   ##.kr    */
/*                                                                            */
/* ************************************************************************** */

#include <iostream>
#include <vector>

using namespace std;

#define IMAX 987654321

int n;
int minResult = IMAX;

bool check(vector<int> &b) {
  int d = b[0] - b[1];

  for (int i = 0; i < n - 1; i++) {
    if (b[i] - b[i + 1] != d) return false;
  }
  return true;
}

void dfs(vector<int> &nb, int i, int count) {
  if (count >= minResult) return;

  if (n == i) {
    if (check(nb)) {
      minResult = min(count, minResult);
    }
    return;
  }

  // 연산하지 않고 다음 dfs로
  dfs(nb, i + 1, count);

  // 현재 인덱스 -1 연산 후 다음 dfs로
  nb[i]--;
  dfs(nb, i + 1, count + 1);
  nb[i]++;

  // 현재 인덱스 +1 연산 후 다음 dfs
  nb[i]++;
  dfs(nb, i + 1, count + 1);
  nb[i]--;
}

int main() {
  cin >> n;
  if (n == 1) {
    cout << "0";
    return 0;
  }

  vector<int> b(n, 0);
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }

  dfs(b, 0, 0);

  if (minResult == IMAX)
    cout << "-1";
  else
    cout << minResult;
  return 0;
}

 

수열 접근 코드. O(9n) = O(900000) 내로 해결 할 수 있었습니다.

#include <iostream>
#include <vector>

using namespace std;

#define IMAX 987654321

int n;
int minResult = IMAX;

void check_arithmetic(const vector<int> &b, int first, int second) {
  int d = second - first;
  int count = 0;

  if (b[0] != first) count++;
  if (b[1] != second) count++;

  int expected = second;

  for (int i = 2; i < n; i++) {
    expected += d;
    if (b[i] == expected)
      continue;
    else if (b[i] - 1 == expected || b[i] + 1 == expected)
      count++;
    else
      return;
  }

  minResult = min(minResult, count);
}

int main() {
  cin >> n;
  vector<int> b(n);
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }

  if (n == 1 || n == 2) {
    cout << "0";
    return 0;
  }

  for (int i = -1; i <= 1; i++) {
    for (int j = -1; j <= 1; j++) {
      check_arithmetic(b, b[0] + i, b[1] + j);
    }
  }

  if (minResult == IMAX)
    cout << "-1";
  else
    cout << minResult;

  return 0;
}