백준 17968 : Fire on Field

 

문제 해석

A[0] = 1, A[1] = 1 이라고 하자. 양수 i >= 2일 때, A[i] 는 아래 조건을 만족하는 가장 작은 양수이다.

k > 0 이고 i - 2k >= 0 일 때,  A[i] - A[i-k] != A[i-k] - A[i-2k]

(예시 생략)

-

음수가 아닌 정수 n을 입력 받을 때, A[n] 값을 출력하라.

 

---

<내 소스>

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> vec_wrong;

void calculate(int(&a_ref)[1001], int i, int k) {
	int wrong = 2 * a_ref[i - k] - a_ref[i - 2 * k];
	vec_wrong.push_back(wrong);
}

int findValue(vector<int>& vec_wrong) {
	int test = 1;
	sort(vec_wrong.begin(), vec_wrong.end());

	for (int i = 0; i < vec_wrong.size(); ++i) {
		if (test == vec_wrong[i]) {
			test++;
		}
	}
	return test;
}

int main() {
	int n;
	int a[1001];
	a[0] = 1;
	a[1] = 1;

	cin >> n;

	for (int i = 2; i <= n; ++i) {
		for (int k = 1; k <= (i / 2); ++k) {
			calculate(a, i, k);
		}
		a[i] = findValue(vec_wrong);
		vec_wrong.clear();
	}
	cout << a[n] << endl;

	return 0;
}

 

 

n은 0부터 1,000까지 입력할 수 있기 때문에 크기 1001의 배열 a를 생성해주고

a[0]과 a[1]의 값을 1로 먼저 초기화해줍니다.  

 

그 다음 n을 입력 받는데 예를 들어, 6을 입력 받았다고 하면 i - 2k >= 0 의 조건을 만족시키는 k는 k <= 3 입니다.

따라서, a[6]을 구하려면 a[6 - k], a[6 - 2 * k] 즉, a[3], a[0], a[4], a[2], a[5] 의 값을 먼저 알아야 합니다. 

n의 값에 따라 모든 a[n] 전의 수열들이 필요한 건 아니지만, 그런 조건까지 따지면 너무 복잡해지기 때문에 여기서 

출력값 a[n]을 구하기 전에 a[2]부터 a[n-1]까지의 값들을 먼저 구해야겠다는 생각을 했습니다.

 

이중for문을 구현해 먼저 calculate 함수를 호출하고 a[2]일 때부터 k 값에 따라 a[i] 가 가질 수 없는 값들을 벡터 vec_wrong에 push 해주었습니다. 이 때, 배열 a는 레퍼런스로 전달했습니다.

 

k값에 따른 vec_wrong 벡터로의 push가 끝나면 findValue 함수를 호출해 벡터를 오름차순으로 정렬하고, for문을 돌려 a[i]가 가질 수 있는 가장 작은 양수를 찾습니다. 이 과정을 i <= n일 때까지 반복하면 구하고자 하는 a[n] 값을 출력할 수 있습니다.

 

여기서 중요한 건 vec_wrong에 든 값들을 clear 함수를 통해 전부 없애는 과정인데 이걸 하지 않으면 엉뚱한 출력값이 나오게 됩니다.  a[n]과 관련 없이 a[n] 이전 수열들이 가질 수 없는 값들까지 같이 배열에 저장되기 때문에 그렇습니다.

 

---

 

여기까지가 제 구현 방법이구요..

밑에 코드는 제가 다른 소스를 살펴보던 중, 저와는 다른 아이디어로 푸신 분이 계셔서 가져와봤습니다.

yooasd11 님의 코드입니다!

 

#include <stdio.h>

bool isPossible(int val, int i, int A[]) {
    for (int k = 1 ; i - 2 * k >= 0 ; ++k) {
        if (A[i] == 2 * A[i - k] - A[i - 2 * k]) {
            return false;
        }
    }
    return true;
}

int main() {
    int n, A[1010];
    scanf("%d", &n);
    
    A[0] = A[1] = 1;
    for (int i = 2 ; i <= n ; ++i) {
        for (int val = 1 ; ; ++val) {
            A[i] = val;
            if (isPossible(val, i, A)) {
                break;
            }
        }
    }
    
    printf("%d\n", A[n]);
}

 

이중 for문에서 첫 번째 for문은 제 코드와 같으나, 두 번째 for문에서 a[i] 의 값을 먼저 1로 지정하고 isPossible 이란 함수를 호출해 a[i] 가 가져서는 안되는 조건의 값과 일치하면(즉, a[i] != 1) false를 return해 val 값을 +1 증가시킵니다. 이 과정을 반복해 a[i]가 가질 수 있는 가장 작은 양수를 찾아 true를 return해주면 break를 만나 첫 번째 for문으로 다시 돌아가게 됩니다.

 

이 방법을 이용하면 함수도 하나 밖에 필요 없고, 쓸데없이 wrong 값을 저장하는 벡터도 생성할 필요가 없기 때문에 제 코드보다 훨씬 좋은 코드인 것 같습니다.

 

 

 

-끝!-