백준 문제풀이

백준 1994 - 등차수열 [Python / C++]

Vermeil 2021. 4. 28. 21:43

www.acmicpc.net/problem/1994

 

1994번: 등차수열

N(1≤N≤2,000)개의 음 아닌 정수들이 있다. 이들 중 몇 개의 정수를 선택하여 나열하면 등차수열을 만들 수 있다. 예를 들어 4, 3, 1, 5, 7이 있을 때 1, 3, 5, 7을 선택하여 나열하면 등차수열이 된다.

www.acmicpc.net

 

정렬 후 이분 탐색

이런거도 dp라고 보는지는 모르겠다.. dp로 푼거는 아닌듯

 

시간복잡도

\(O(N^2 logN)\)

 

 

[Python]

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
34
35
36
37
38
39
40
41
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**4)
 
def f(prv, d, ret):
    lo = 0; hi = len(a)-1
    while lo<hi:
        mid = (lo+hi)//2
        if a[mid]<prv+d:
            lo = mid+1
        elif a[mid]>prv+d:
            hi = mid-1
        else:
            lo = mid
            break
    if a[lo] == prv+d:
        return f(a[lo], d, ret+1)
    return ret
 
n=int(input())
arr=[]
a=[]
for i in range(n):
    arr.append(int(input()))
arr.sort()
 
ans = 1
now = 1
a=[arr[0]]
for i in range(1, n):
    if arr[i]==arr[i-1]:
        now += 1
    else:
        ans = max(ans,now)
        now = 1
        a.append(arr[i])
ans = max(ans,now)
for i in range(len(a)):
    for j in range(i+1,len(a)):
        ans = max(ans, f(a[i], a[j]-a[i], 1))
print(ans)
 cs

 

 

[C++]

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
 
vector<ll>arr;
vector<ll>a;
int f(ll prv, ll d, int ret){
    int lo=0;
    int hi=a.size()-1;
    while(lo<hi){
        int mid=(lo+hi)/2;
        if(a[mid]<prv+d){
            lo=mid+1;
        }
        else if(a[mid]>prv+d){
            hi=mid-1;
        }
        else{
            lo = mid;
            break;
        }
    }
    if (a[lo] == prv+d){
        return f(a[lo], d, ret+1);
    }
    return ret;
}
 
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n;
    cin >> n;
 
    for(int i=0;i<n;i++){
        ll p;
        cin >> p;
        arr.push_back(p);
    }
 
    sort(arr.begin(),arr.end());
    int ans = 1;
    int now = 1;
    a.push_back(arr[0]);
 
    for (int i=1;i<n;i++){
        if(arr[i]==arr[i-1]){
            now++;
        }
        else{
            ans = max(ans,now);
            now=1;
            a.push_back(arr[i]);
        }
    }
    ans = max(ans,now);
    for (int i=0;i<a.size();i++){
        for (int j=i+1;j<a.size();j++){
            ans = max(ans, f(a[i], a[j]-a[i], 1));
        }
    }
    cout << ans;
}
 
 cs

 

 

질문, 오류 지적 등등 환영합니다.

저작자표시