백준 25401번 카드 바꾸기 (C++)

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

25401번: 카드 바꾸기

 

수학적인 테크닉이 조금 필요한 문제이다. 일정하게 증가,감소 수열을 만들어야하기 때문에 처음 떠오른 방식은 dp, 이분탐색이었다.

 

1. DP : 내가 DP를 잘 못하기도 하고 어떻게 점화식을 짜야할지 감이잡히지 않았다.

2. 이분탐색: 숫자의 범위가 -100만~ 100만이기 때문에 이분탐색을 떠올리고 가장 최적의 증가, 감소치를 찾으면 될 것이라 생각하였으나. 만약 4를 공차라고 하였을 때 결과가 10이라 한다면 이 때 이분탐색으로 upper탐색을 할 지 lowwer 탐색을 할 지 결정할 수 없다.

 

문제의 열쇄는 " 두 개의 카드를 고른 후 이 두개의 카드는 바뀌지 않는다 "를 생각해내면 문제가 풀린다. 

 

2 9 1 2 10 라 할 때 2와 10을 선택했다고 가정하자. 그렇다면 인덱스는 i = 0, j = 4라고 가정할 수 있다.

 

그리고 이 둘이 바뀌지 않을 떄. 즉 이 두 카드를 기준으로 공차를 만들었을 때 답이라고 가정하면 

 

value[i] - value[j] / i - j = -8 / -4 = 2

 

이제 i 혹은 j를 기준으로 양옆을 전부 공차가 2인 경우로 바꿔주면서 만약 원래 값과 같다면 카운팅하지 않으면 된다.

이 경우 두개를 고정하고, N번을 돌아야 하므로 총 시간 복잡도는 O(N^3)으로 문제를 해결할 수 있다.

 

#include <iostream>
#include <vector>
using namespace std;

vector<int> card;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;
	card = vector<int>(N);
	for (int i = 0; i < N; i++) {
		cin >> card[i];
	}
	int answer = 501;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int cnt = 0;
			if (i == j || (card[i] - card[j]) % (i - j) == 0) {
				int gap;
				if (i == j) gap = 0;
				else gap = ((card[i] - card[j]) / (i - j));
				vector<int> tmp = card;
				for (int k = i + 1; k < N; k++) {
					int value = gap + tmp[k - 1];
					if (value != card[k]) cnt++;
					tmp[k] = value;
				}

				for (int k = i - 1; k > -1; k--) {
					int value = tmp[k + 1] - gap;
					if (value != card[k]) cnt++;
					tmp[k] = value;
				}

				answer = min(answer, cnt);
			}
		}
	}

	cout << answer << '\n';
}