백준 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억까지 가능하다고 해서 일단 다음과 같이 돌려보았다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#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]);
}
|
cs |
다행히 통과했지만 더 좋은 방법이 있을 것 같아 구글링해보았다
나는 무조건 다 담아서 해야 한다고 생각했는데 담는 대신 그때그때 바로 비교해서 가장 작은 값을 찾을 수 있었다
최적의 풀이로는 못풀었지만 A번이라 쉬웠던 문제
'알고리즘' 카테고리의 다른 글
[ICPC] Working Plan (0) | 2020.09.22 |
---|---|
[ICPC] What’s Mine is Mine (0) | 2020.09.15 |
[C++] 백준 5052번 : 전화번호 목록 (0) | 2020.06.13 |
[C] 백준 3978번 : Hacking (0) | 2020.06.13 |
[C] 백준 17144번 : 미세먼지 안녕! (0) | 2020.06.13 |