문제 URL : https://www.acmicpc.net/problem/17088
17088번: 등차수열 변환
크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1]��
www.acmicpc.net
문제 접근법 : 연산을 최대 1번 ,즉 1을 더하거나 혹은 1을빼거나 혹은 안하거나 해서
등차수열을 만다는 거지만 이것을 어떻게 만드냐에 따라 시간초과나느냐 안나느냐 문제입니다.
단순하게 정말로 모든 경우의수를 만들고난후 첫번째인덱스부터 n번째 인덱스까지 확인해서 공차가
같은지 확인한다면 100% 시간 초과납니다. n이 최대 50만이기때문에
하지만 최대한 가지치기를 해서 backtrack을 이용한다면 빠른 알고리즘을 만들수있는데
방법은 처음 v[1]-v[0] 의 공차를 담아내는 변수 dif를 만들고 인덱스 2번부터시작해서 v[i]-v[i-1]의 공차가 dif와 같은지확인해서 backtrack를 돈다면 충분히 시간초과를 벗어날수 있습니다.
단 v[1]-v[0]을 먼저 진행했기때문에 이두개의 변수도 1을 더하고 빼고 안더하고 하는 식을 만들어줘야하기 때문에
backtrack를 총 9번 돌려야 답이 나옵니다.
소스코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
nclude <iostream>
#include <vector>
#include <cstring>
#include <string>
using namespace std;
int n;
vector<int> v;
int Min = 1e+9;
int diff(int a, int b)
{
return b - a;
}
void dfs(int before, int idx, int cnt, int dif){
if (idx >= n)//이곳까지 왔다면 공차가 다같은경우
{
Min = Min > cnt ? cnt : Min;
return;
}
int nextdif = v[idx] + 1 - before;//현재 1을 더한경우
if (nextdif == dif)
dfs(v[idx] + 1, idx + 1, cnt + 1, dif);
nextdif = v[idx] - 1 - before;//현재 1을 뺀경우
if (nextdif == dif)
dfs(v[idx] - 1, idx + 1, cnt + 1, dif);
nextdif = v[idx] - before;
if (nextdif == dif)
dfs(v[idx], idx + 1, cnt, dif);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++)
cin >> v[i];
int dif = diff(v[0] + 1, v[1] + 1);
dfs(v[1] + 1, 2, 2, dif);
dif = diff(v[0] - 1, v[1] + 1);
dfs(v[1] + 1, 2, 2, dif);
dif = diff(v[0], v[1] + 1);
dfs(v[1] + 1, 2, 1, dif);
dif = diff(v[0] + 1, v[1] - 1);
dfs(v[1] - 1, 2, 2, dif);
dif = diff(v[0] - 1, v[1] - 1);
dfs(v[1] - 1, 2, 2, dif);
dif = diff(v[0], v[1] - 1);
dfs(v[1] - 1, 2, 1, dif);
dif = diff(v[0] + 1, v[1]);
dfs(v[1], 2, 1, dif);
dif = diff(v[0] - 1, v[1]);
dfs(v[1], 2, 1, dif);
dif = diff(v[0], v[1]);
dfs(v[1], 2, 0, dif);
if (Min == 1e+9)
cout << -1 << "\n";
else
cout << Min << "\n";
}
|
cs |
모르는것이나 궁금한점이 있다면 언제든 댓글을 이용해주시길바랍니다.
'백준' 카테고리의 다른 글
| 백준 2178 미로 탐색 (0) | 2020.08.06 |
|---|---|
| 백준 1822 차집합 (0) | 2020.08.06 |
| 백준 16197 두 동전 (0) | 2020.07.31 |
| 백준 14225 부분수열의 합 (0) | 2020.07.31 |
| 백준 16948 데스 나이트 (0) | 2020.07.31 |