-
백준 17088번 등차수열 변환PS 2020. 3. 15. 23:29
https://www.acmicpc.net/problem/17088
<접근방법>
모든 수에 대하여 -1, 0, +1 연산을 적용시켜서 경우의 수를 계산하면 N의 크기가 10^5이기 때문에
시간 초과가 납니다.
인접한 숫자들은 서로 연관되어 있습니다.
뒤에 있는 숫자가 앞의 숫자에 맞춰서 등차수열의 관계를 유지할 필요가 있습니다.
이렇게 생각한다면 모든 경우의 수들에 대해서 생각할 필요가 없어집니다.
앞의 숫자의 스탠스만 정해주면 되니까요.
<느낀 점>
<코드>
#include <iostream> #include <algorithm> using namespace std; int n; int a[100001], b[100001]; void reset() { for (int i = 0; i < n; i++) { a[i] = b[i]; } } int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; b[i] = a[i]; } if (n == 1) { cout << 0 << '\n'; exit(0); } int res = 987654321; for (int i = -1; i <= 1; i++) { for (int j = -1; j <= 1; j++) { reset(); int tres = 0; if (i != 0) tres++; if (j != 0) tres++; a[0] += i; a[1] += j; int diff = a[0] - a[1]; bool suc = true; for (int k = 2; k < n; k++) { int tdiff = a[k-1] - a[k]; bool flag = false; for (int l = -1; l <= 1; l++) { if (tdiff + l == diff) { flag = true; a[k] -= l; if (l != 0) { tres++; } break; } } if (!flag) { suc = false; break; } } if (suc) { res = min(res, tres); } } } if (res == 987654321) cout << -1 << '\n'; else cout << res << '\n'; return 0; }
'PS' 카테고리의 다른 글
백준 16937번 두 스티커 (0) 2020.03.15 백준 16638번 괄호 추가하기2 (0) 2020.03.15 백준 13913번 숨바꼭질4 (0) 2020.03.10 백준 13549번 숨바꼭질 3 (0) 2020.03.10 백준 12851번 숨바꼭질2 (0) 2020.03.10