https://www.acmicpc.net/problem/2003



n이 10000 이하이고, 시간 제한이 0.5초이기 때문에, n^2 풀이로 풀게 되면 시간 초과가 날 것이다.


따라서 O(n)에 해결할 수 있도록 투포인터를 사용하도록 한다.



초기에 st와 en을 모두 시작점으로 정해두고, en이 범위 밖으로 벗어날 때까지 진행해준다.



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
#include<iostream>
 
using namespace std;
int n, m, arr[10001];
int main(void) {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    int st = 0, en = 0, cnt = 0;
    long long Sum = arr[0];
 
    while (1) {
        //합이 부족해서 en이 우측으로 움직이는 건데, en이 밖으로 나갔다는 것은 더 볼 필요가 없다는 것
        //st가 우측으로 움직여봤자 합은 더 감소하기 때문에
        if (en >= n) break; 
        
        if (Sum == m) {
            Sum += arr[++en]; //딱 만족할 때 en 증가
            cnt++;
        }
 
        else if (Sum < m) Sum += arr[++en];
 
        else {
            
            Sum -= arr[st++];
            if (st > en) {
                en = st;
                Sum = arr[en];
            }
        }
    }
    cout << cnt;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1339번: 단어 수학 (C++)  (0) 2019.08.29
백준 1644번: 소수의 연속합 (C++)  (0) 2019.08.29
백준 13458번: 시험 감독 (C++)  (0) 2019.08.29
백준 14500번: 테트로미노 (C++)  (0) 2019.08.29
백준 14503번: 로봇 청소기 (C++)  (0) 2019.08.28

An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

  • A[P] + A[Q] > A[R],
  • A[Q] + A[R] > A[P],
  • A[R] + A[P] > A[Q].

For example, consider array A such that:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20

Triplet (0, 2, 4) is triangular.

Write a function:

int solution(vector<int> &A);

that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

For example, given array A such that:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20

the function should return 1, as explained above. Given array A such that:

A[0] = 10 A[1] = 50 A[2] = 5 A[3] = 1

the function should return 0.

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [0..100,000];
  • each element of array A is an integer within the range [−2,147,483,648..2,147,483,647]


문제는 위와 같다.


조건은 저렇게 위에 세 개의 부등식으로 나와있지만, 정렬을해서 확인하면 작은 두 원소의 합이 가장 큰 원소보다 크면 성립하게 된다.


오버플로우 방지를 위해 하나의 항을 이항해서 계산해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
#include <algorithm>
int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.size() < 3) return 0;
    sort(A.begin(), A.end());
    for(int i = 0 ; i <= A.size()-3 ; i++){
        if(A[i] > A[i+2]-A[i+1]) //오버플로우 방지
            return 1;
    }
    return 0;
}
 
cs


저작자표시 비영리 변경금지

https://www.acmicpc.net/problem/13458



총감독관은 무조건 1명은 존재해야 하기 때문에 기본적으로 답은 n부터 시작한다.


시험장마다의 인원보다 b가 크다면, 총감독관 혼자 커버할 수 있기 때문에 시험장 인원을 0으로 갱신해준다.


그렇지 않다면 시험장 인원에서 총감독관이 감시하고 있는 인원의 수인 b를 감소시켜준다.



다음으로 필요한 부감독관의 수를 계산한다. 1명이라도 부감독관이 감시할 수 있는 사람보다 수가 많으면 부감독관 한 명이 더 필요하기 때문에, 갱신한 시험장 인원을 c로 나눈 나머지가 0인지 아닌지에 따라서 부감독관의 인원을 정한다.



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
#include<iostream>
#include<algorithm>
using namespace std;
int n, arr[1000001], b, c;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> arr[i];
    cin >> b >> c;
 
    for (int i = 0; i < n; i++) {
        if (arr[i] <= b) arr[i] = 0;
        else arr[i] -= b;
    }
    
    long long ans = n;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] % c != 0) ans = ans + (arr[i] / c) + 1;
        else
            ans = ans +  (arr[i] / c);
    }
    cout << ans;
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1644번: 소수의 연속합 (C++)  (0) 2019.08.29
백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29
백준 14500번: 테트로미노 (C++)  (0) 2019.08.29
백준 14503번: 로봇 청소기 (C++)  (0) 2019.08.28
백준 14888번: 연산자 끼워넣기 (C++)  (0) 2019.08.27

https://www.acmicpc.net/problem/14500


이차원 배열로 주어지는 격자에서, 모든 테트로미노 모양을 다 넣어보면 된다.


주어지는 다섯개의 테트로미노를 회전 또는 대칭해서 얻을 수 있는 모양들까지 포함해서 계산해주면 된다.


가능한 모양은 총 19개이다.


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
#include<iostream>
#include<vector>
using namespace std;
int row, col, m[501][501];
int Max = -1;
 
//가능한 모양은 총 19개이다
vector<int> vr[19] = { { 1,2,3 },{ 0,0,0 },{ 0,1,1 },{ 1,2,2 },{ 0,0,-1 },{ 0,1,2 },{ -1,-1,-1 },{ 0,0,1 },{ -1,0,1 },{ -1,0,0 },{ 1,1,2 },{ 1,1,2 },
{ 0,-1,-1 },{ -1,-1,-2 },{ 0,1,1 },{ 0,-1,-2 },{ 1,1,1 },{ -1,-2,-2 },{ 0,0,1 } };
 
vector<int> vc[19] = { { 0,0,0 },{ 1,2,3 },{ 1,0,1 },{ 0,0,1 },{ 1,2,2 },{ 1,1,1 },{ 0,1,2 },{ 1, 2, 1 },
{ 1,1,1 },{ 1,1,2 },{ 0,1,0 },{ 0,1,1 },{ 1,1,2 },{ 0,1,1 },{ 1,1,2 },{ 1,1,1 } ,{ 0,1,2 } ,{ 0,0,1 } ,{ 1,2,2 } };
 
void calculate() {
    int cnt = 0;
    for (int con = 0; con < 19; con++) {
 
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int Sum = m[i][j];
                bool isBreak = false;
 
                for (int k = 0; k < 3; k++) {
                    int nr = i + vr[con][k];
                    int nc = j + vc[con][k];
                    if (nr < 0 || nc < 0 || nr >= row || nc >= col) {
                        isBreak = true;
                        break;
                    }
                    Sum += m[nr][nc];
 
                }
                if (!isBreak)
                    if (Sum > Max) Max = Sum;
            }
        }
    }
 
}
int main(void) {
    cin >> row >> col;
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            cin >> m[i][j];
 
    calculate();
    cout << Max << '\n';
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29
백준 13458번: 시험 감독 (C++)  (0) 2019.08.29
백준 14503번: 로봇 청소기 (C++)  (0) 2019.08.28
백준 14888번: 연산자 끼워넣기 (C++)  (0) 2019.08.27
백준 11328번 Strfry (C++)  (0) 2019.08.25

삽입 정렬에 대해 정리해보자.


삽입 정렬은, 선택 정렬 그리고 버블 정렬과 함께 대표적인 시간 복잡도 O(n^2) 알고리즘이다.



하지만 삽입 정렬은, 필요할 때까지만 삽입(스왑)이 일어나기 때문에, 정렬할 배열이 거의 정렬되어 있는 상태라면 다른 선택 정렬, 버블 정렬보다 훨씬 빠른 속도를 보여준다.



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
#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{   
 
    int a[10] = {-100, 10, 13, -5, 4, 12 , -5, 6, -1000, 2};
    
    int n = 10;
   
   //삽입 정렬 오름차순
   for(int i = 0 ; i < n - 1 ; i++){ //while문 내부 비교 구문에서, j와 j+1을 비교하기 때문에 n-2까지만 들어가도록
       int j = i;
       while(j >= 0 && a[j] > a[j + 1]){ //i의 앞쪽까지는 이미 정렬이 돼있다고 본다.
           swap(a[j], a[j + 1]); //따라서 swap이 일어나지 않으면 그 cycle의 정렬은 끝난 것
           j--;
       }
   }
    
    for(int i = 0 ; i < 10 ; i++)
        cout << a[i] << ' ';
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'Computer Science > Algorithm Theory' 카테고리의 다른 글

C++ 알고리즘 체크리스트  (0) 2021.10.16
퀵, 머지, 힙 정렬 알고리즘 간단 정리  (0) 2019.10.06
버블 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
선택 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
Counting Sort (C++)  (0) 2019.08.23

+ Recent posts

티스토리툴바