문제링크 : https://www.acmicpc.net/problem/2467


아이디어

  • 각 숫자를 순회하면서 0에 가까운 수를 찾으면
    • O(N^2) = 1e10 > 시간초과
  • 한 숫자를 정하고 나머지 숫자에 대해서 반대값을 이진탐색
    • O(N * lgN)
  • lower ? upper ?
    • lower로 찾고, 만약 0보다 클경우, 하나 인덱스 뺀것도 같이 계산해주자
  • 이진탐색 범위
    • 오름차순이기 때문에, 자기 자신의 다음위치만 찾으면 됨
    • 자기자신 이전에 있을 경우는 어짜피 쌍으로되기때문에 이전에서 찾아줌

시간복잡도 계산

  • 모든 숫자에 대해서 : O(N)
  • 이진탐색 진행 : O(lgN)
  • 시간복잡도 : O(N*lgN) : 1e5 * 20 = 2e6

인트 계산

  • 최소값 2개 더할경우 : -2e9
  • 최대값 2개 더할경우 : 2e9
  • 인트 사용 가능

코드

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
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> nums;
 
int binsearch(int st, int en, int tar) {
    if(st==en) return st;
    
    int mid = (st+en)/2;
    if(nums[mid] < tar) return binsearch(mid+1, en, tar);
    else return binsearch(st, mid, tar);
    
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    for(int i=0; i<N; i++) {
        int a; cin >> a;
        nums.push_back(a);
    }
    
    int minv =2e9+10;
    int fn = -1;
    int sn = -1;
    
    // 모든 숫자에 대해서, 마지막은 빼주기
    for(int i=0; i<N-1; i++) {
        int eachNum = nums[i];
        
        // eachNum에 반대되는값을 이진탐색
        int target = eachNum * -1;
        int idx = binsearch(i+1,nums.size()-1, target);
        
        // idx 이전값이랑 비교할때, 같은 값이 아닌지 주의
        if(idx >0 && idx-1 != i) {
            if( abs(nums[idx] + eachNum) > abs(nums[idx-1] + eachNum)) idx = idx-1;
        }
        
        if(minv > abs(nums[idx] + eachNum)) {
            minv =abs(nums[idx] + eachNum);
            fn = eachNum;
            sn = nums[idx];
        }
        
    }
    
    if(fn > sn) cout << sn << ' ' << fn << '\n';
    else cout << fn << ' ' << sn << '\n';
    
    
    
    return 0;
}
 
cs

문제유형

  • 이진탐색 - 리스트 내의 값으로 이진탐색
    • 리스트 안에 있는 값중 하나로, 자기와 반대되는 값을 탐색
    • 자기 자신부터 끝까지 이진탐색 수행
    • 마지막 원소는 이진탐색 해주지 않음
    • 쌍을 찾는것이기 때문에 마지막 원소는 찾지 않아도됨

'알고리즘 > 백준' 카테고리의 다른 글

백준 1248 맞춰봐 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2169 로봇 조종하기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1915 가장 큰 정사각형 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1339 단어수학 쉬운 풀이 (C++/CPP)  (0) 2021.02.16
백준 1107 리모컨  (1) 2021.02.16

아이디어

  • 그래프 순회하면서 대각선만 DFS로 가면 안될까?
    • 노드 개수 : O(N^2)
    • 각 노드에서 순회해야할 갯수, 대각선만 보면 됨, O(N)
    • O(N^3) = 1e9 > 시간초과
  • 이전에 구한 정사각형을 다음에 활용 가능? > DP 사용
    • DP[j][i] = j, i칸에서 가장 큰 정사각형의 크기
    • 해당 노드가 0일경우 넘어감
    • 해당 노드가 1일경우, 왼쪽, 왼쪽위 대각선, 위쪽 중 가장 작은값에 1 더한 값으로 갱신

시간복잡도 계산

  • O(N^2) 순회
  • 각 노드에서 3개 지점만 확인
    • 시간복잡도 : O(3*N^2) = 3e6

인트 계산

  • 정사각형 크기 : 최대 1e6 > INT 사용 가능

코드

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
#include <iostream>
#include <string>
 
using namespace std;
 
int dp[1010][1010];
int map[1010][1010];
int main() {
    //dp 초기화
    fill(&dp[0][0], &dp[1009][1010], 0);
    
    int N,M; cin >> N >> M;
    for(int j=0; j<N; j++) {
        string s; cin >> s;
        for(int i=0; i<M; i++) {
            map[j][i] = s[i]-'0';
        }
    }
    
    int maxv = 0;
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            if(j==0 || i==0) dp[j][i] = map[j][i];
            else if(map[j][i] == 1){
                // 3방향중 가장 작은 값에다 1더한값으로 갱신
                dp[j][i] = min(min(dp[j-1][i], dp[j-1][i-1]), dp[j][i-1]) + 1;
            }
            maxv = max(maxv, dp[j][i]);
        }
    }
    
    cout << maxv*maxv << '\n';
    return 0;
}
 
cs

문제유형

  • DP - 2차원 배열
    • 단순히 모양이 2차원일뿐, 1차원 DP와 같이 앞의 값을 활용해 풀면 됨

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 2169 로봇 조종하기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2467 용액 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1339 단어수학 쉬운 풀이 (C++/CPP)  (0) 2021.02.16
백준 1107 리모컨  (1) 2021.02.16
백준 2143 두 배열의 합 쉬운 풀이(C++/CPP)  (0) 2021.02.15

문제 추상화

  • 알파벳에 숫자를 대입해서 최대의 수를 찾는문제
  • 앞자리일수록 큰게 좋음 >> 그리디 - 숫자

아이디어

  • 모든 숫자를 알파벳에 대입해서 최대값을 찾는 경우
    • 시간복잡도가 관건
    • 시간복잡도 : 알파뱃 최대 갯수 ^ 알파벳 최대갯수 > 10^10 > 시간초과
  • 앞자리일수록 큰 숫자로
    • 만약 두개의 단어가 길이가 같은데 첫자리가 다른경우?
    • 뒤에 더 앞자리가 들어오는 알파벳에 큰 숫자를 넣어야함
    • 각 알파벳이 들어간 위치를 계산하여 점수를 매기는 수밖에없음
  • 단어의 길이를 먼저 구함
  • 단어의 위치에서 알파벳의 평가점수를 넣어줌
  • 평가점수가 높은 순으로 높은 숫자를 넣음
  • 단어의 합을 구함

시간복잡도 계산

  • 모든 단어에 대해서 : O(N)
  • 단어의 길이를 먼저 구함 : O(1)
  • 단어의 위치에서 알파벳의 평가점수를 넣어줌 : O(10)
  • 평가점수가 높은 순으로 높은 숫자를 넣음
  • 단어의 합을 구함 : O(N)
  • 시간복잡도 : O(N*10 + N) : O(10N) = 100

인트 계산

  • 단어의 합 최대값 : 10 * 9999999999 = 1e11 >> long long 사용
  • 알파벳의 평가점수 : 평가점수 최대값 : 10 * 1e10 >> long long 사용

코드

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
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int alpha[26];
 
int main() {
    int N; cin >> N;
    
    fill(alpha, alpha+26, 0);
    
    for(int i=0; i<N; i++) {
        string s; cin >> s;
        for(int i=0; i<s.size(); i++) {
            // 알파벳 숫자로 변환
            int ec = s[i] - 'A';
            // 알파벳 평가점수
            alpha[ec] += pow(10,s.size()-1-i);
        }
    }
    
    sort(alpha, alpha+26, greater<int>());
    
    int rs=0;
    int tmp = 10;
    
    for(int i=0; i<10; i++) {
        tmp--;
        rs += alpha[i] * tmp;
    }
    
    cout << rs << '\n';
    
    return 0;
}
 
cs

문제유형

  • 그리디 - 숫자관련 최소 최대
    • 최대 : 앞자리일수록 큰 수 사용, 최소는 그 반대
    • 엣지값 -1,0,1 조심

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 2467 용액 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1915 가장 큰 정사각형 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1107 리모컨  (1) 2021.02.16
백준 2143 두 배열의 합 쉬운 풀이(C++/CPP)  (0) 2021.02.15
백준 2565 전깃줄 쉬운 풀이(C++/CPP)  (0) 2021.02.15

+ Recent posts

티스토리툴바