[ICPC] Fire on Field

백준 17968번으로 풀어본 ICPC 지역 예선 문제

 

Let A[0] = 1, A[1] = 1. For a positive integer i ≥ 2, A[i] is the smallest positive integer under the condition that no three terms A[i − 2k], A[i − k], and A[i] form an arithmetic progression for any integer k > 0 such that i − 2k ≥ 0, that is, A[i] − A[i − k] ≠ A[i − k] − A[i − 2k].

 

이러한 조건을 만족하는 배열에서 n번째 값을 찾는 문제이다

다 찾으면 이런식으로 분포가 된다고 한다

 

n의 범위가 1000까지밖에 안되길래 웬만한 풀이로는 다 풀 수 있을 것이라고 생각했다

단순히 생각해본 최악의 상황은 1000개 모두 안되는 숫자 500개를 찾아서 그 500개를 뒤지는 것이었다

1000*500*500 = 2.5억이라 시간 제한 1초면 보통 1~3억까지 가능하다고 해서 일단 다음과 같이 돌려보았다

#include <stdio.h>
#include <set>
 
using namespace std;
 
int DP[1001];
 
int main(){
    DP[0] = 1;
    DP[1] = 1;
    int n;
    scanf("%d",&n);
    for(int i = 2 ; i <= n ; i++){
        set <int, less<int> > s;
 
        for(int k = 1 ; i - 2*k >= 0 ; k++){
            s.insert((2*DP[i-k]-DP[i-2*k]));
        }
        int prev = 1, len = s.size();
        for(auto it = s.begin() ; it != s.end() ; it++){
            if(*it<1) continue;
            if(*it == prev){
                prev++;
            }
            else{
                DP[i]=prev;
                break;
            }
        }
        if(DP[i]==0) DP[i] = prev;
    }
    printf("%d\n",DP[n]);
}

다행히 통과했지만 더 좋은 방법이 있을 것 같아 구글링해보았다

나는 무조건 다 담아서 해야 한다고 생각했는데 담는 대신 그때그때 바로 비교해서 가장 작은 값을 찾을 수 있었다

최적의 풀이로는 못풀었지만 A번이라 쉬웠던 문제