ACPC 2019 - A Fire on Field 한국어 번역, 문제 풀이

 

 

1. 문제

 문제 요악 하면

 - 수열은 수열인데

 - 앞의 어떤 수와도 등차수열이 아닌!!

 - 즉, 앞의 어느 수와도 A[i] - A[i-k] != A[i-k] - A[i-2k]를 만족하지 않는

 - 근데 그 중에서 가장 작은 수를 원소로 가지는

 - 수열을 찾아라

 

2. 필요한 배경지식 + 풀이 방법

 - 요즘 다이나믹 프로그래밍을 많이해서 그런가 DP라고 생각을 해서 앞의 차를 다 cache로 가지고 있으려고 했는데

 - 어차피 가장 작은수를 찾는 거여서 수가 그렇게 커지지 않아

 - 하나하나 조건에 일치하는지 따져보는 것으로 전략을 바꾸었다. 

 

3. 풀이

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

//지금 오는 숫자가 앞에, 앞에 나왔었던 숫자가 뒤에
//자기 고유의 숫자 cache[index][0]
int cache[1001][1001];

//앞의 숫자들의 차를 저장하는 cache인데 필요없다,,
void fillcache(int index) {
	for (int i = 1; i < index; i++) {
		cache[index][i] = cache[index][0] - cache[i][0];
	}
}

//test == 0부터 그냥 찔러보는 숫자
int findNum(int target, int test) {
	bool result = true;
	for (int k = 1; k <= (target / 2); k++) {
		if ((test - cache[target - k][0]) == (cache[target - k][0] - cache[target - (2 * k)][0])) {
		result = false;
		break;
	}
	}
	
	if (result) return test;
	else return -1;
}

int main() {
	int n;
	cin >> n;
	//처음에 알려준 cache 값
	cache[0][0] = 1;
	cache[1][0] = 1;
    
	//절대 나올 수 없는 음수
    int m = -1;
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < n; j++) { //최소 원소 크기가 1임
			m = findNum(i, j);
			if(m != -1) break;
		}
		cache[i][0] = m;
		fillcache(i);
	}
	cout << cache[n][0];
}

 

 근데 쓸데없이 메모리를 많이 차지한다는 점에서 좋은 코드는 아니다.. 

 그냥 바로 일치하는지 아닌지 메인에서 돌려봐도 충분할듯

 암튼 이런 별로인 코드도 시간초과 없이 풀린당^^*

 

4. 결과 화면

담엔 더 좋은 코드로 돌아오겠당^^*//