문제 : https://www.acmicpc.net/problem/9881

[ 문제해석 ]

 N개의 언덕을 가지고 있는데 가장 높은 언덕와 가장 낮은 언덕의 차이를 17 이내로 만들어야된다. 언덕을 k 만큼 쌓거나 깎는데 k * k 만큼의 cost가 발생한다. 이때, 필요한 가장 적은 cost는 얼마인가

 

[ 알고리즘풀이 ]

 N 은 최대 1000, 언덕의 높이도 0 ~ 100 으로 범위가 작다. 즉, 모든 경우에 대해서 cost를 구해봐도 시간 초과에 걸리지 않는다.

 --> 0 ~ 17 / 1 ~ 18 / 2 ~ 19 / .... / 83 ~ 100 과 같이 크기가 17인 모든 범위를 나눈 후, 각 범위마다 N개의 언덕을 순회하며 깎거나 쌓아본다.

 

[ 코드 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
#include<iostream>
#include<algorithm>
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N, hills[1000];
 
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> hills[i];
 
    int ans = 99999999;
    for (int i = 0; i <= 100 - 17; i++) {
        // i ~ i + 17 까지가 우리가 잡은 범위!
        int tempAns = 0;
        for (int j = 0; j < N; j++) {
            if (hills[j] < i) tempAns += (i - hills[j]) * (i - hills[j]);
            if (hills[j] > i + 17) tempAns += (hills[j] - i - 17) * (hills[j] - i - 17);
        }
        ans = min(ans, tempAns);
    }
    cout << ans << '\n';
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ9881.cpp

 

travelbeeee/ProblemSolving

백준 문제풀이. Contribute to travelbeeee/ProblemSolving development by creating an account on GitHub.

github.com

 

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 15711 : 환상의 짝궁  (0) 2020.08.27
[BOJ] 1826 : 연료 채우기  (1) 2020.08.26
[BOJ] 13711 : LCS 4  (0) 2020.08.25
[BOJ] 2632 : 피자판매  (0) 2020.08.24
[BOJ] 11964 : Fruit Feast  (0) 2020.08.23

문제 : https://www.acmicpc.net/problem/13711

DP 동적프로그래밍

[ 알고리즘풀이 ]

 입력으로 주어지는 배열 B의 Index를 A 배열을 기준으로 정렬하면 LIS 문제로 바뀌게 된다.

  Sorted배열 [ 3 0 4 1 2 5 ] 에서 가장 긴 LIS는 [ 0 1 2 5 ] 가 되고 이는 다시 생각해보면 B배열의 0, 1, 2, 5 인덱스이므로 실제 B배열에서 [ 1 4 5 6 ] 을 의미한다.

( O(NlogN) 으로 LIS구하기 :  https://travelbeeee.tistory.com/455?category=800452) 

 

[ 코드 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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int LIS(vector<int> v) {
    const int INF = 99999999;
    int N = v.size();
    vector<int> Dp(N + 1, INF);
    int longest = 1;
    Dp[0] = -INF;
    Dp[1] = v[0];
    for (int cur : v) {
        if (Dp[longest] < cur) {
            longest++;
            Dp[longest] = cur;
        }
        else {
            vector<int>::iterator it = lower_bound(Dp.begin(), Dp.end(), cur);
            *it = cur;
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++)
        if (Dp[i] != INF) ans = i;
    return ans;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N;
    cin >> N;
    
    vector<int> A(N);
    vector<int> temp(N);
    vector<int> index(N);
 
    for (int i = 0; i < N; i++)
        cin >> A[i];
 
    for (int i = 0, x; i < N; i++) {
        cin >> x;
        temp[x - 1] = i;
    }
 
    for (int i = 0; i < N; i++)
        index[i] = temp[A[i] - 1];
 
    cout << LIS(index);
    
}
 cs

[ github]

https://github.com/travelbeeee/BOJ/blob/master/BOJ13711.cpp

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 1826 : 연료 채우기  (1) 2020.08.26
[BOJ] 9881 : Ski Course Design  (0) 2020.08.25
[BOJ] 2632 : 피자판매  (0) 2020.08.24
[BOJ] 11964 : Fruit Feast  (0) 2020.08.23
[BOJ] 18808 : 스티커 붙이기  (0) 2020.08.23

문제 : https://www.acmicpc.net/problem/2632

누적합

[ 알고리즘풀이 ]

 문제 Input 크기를 유심히 들여다보면 쉽게 해결할 수 있는 문제다.

 최대 피자 조각이 1000개이므로 우리는 피자 조각이 연속된 합을 모두 구해보아도 O(N^2) 으로 시간 초과에 걸리지 않는다. 또한, 피자 조각의 크기가 최대 1000이므로 연속된 합이 1000 * 1000 을 넘어가지 않으므로, 10^6 크기의 int 배열로 가능한 모든 피자 조각의 연속된 합을 count 할 수 있다.

 A / B 피자별로 가능한 모든 피자 조각의 연속된 합을 count 하고 난 후, client 가 원하는 크기를 A와 B 피자에서 조각을 꺼내와 만들면 답을 쉽게 구할 수 있다.

 

[ 코드 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
#include<iostream>
 
using namespace std;
 
int client, nA, nB;
int pizzaA[1000], pizzaB[1000]; // pizza 조각들
int sizeA[1000001] = {}, sizeB[1000001] = {}; // pizza 조각으로 만들 수 있는 크기 count
int ans = 0;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> client >> nA >> nB;
    for (int i = 0; i < nA; i++)
        cin >> pizzaA[i];
    for (int i = 0; i < nB; i++)
        cin >> pizzaB[i];
 
    sizeA[0] = 1, sizeB[0] = 1; 
    int sum = 0;
    for (int i = 0; i < nA; i++)
        sum += pizzaA[i];
    sizeA[sum]++;
    sum = 0;
    for (int i = 0; i < nB; i++)
        sum += pizzaB[i];
    sizeB[sum]++;
 
    for (int i = 0; i < nA; i++) {
        int sum = 0;
        for (int j = 0; j < nA - 1; j++) {
            sum += pizzaA[(i + j) % nA];
            sizeA[sum]++;
        }
    }
    for (int i = 0; i < nB; i++) {
        int sum = 0;
        for (int j = 0; j < nB - 1; j++) {
            sum += pizzaB[(i + j) % nB];
            sizeB[sum]++;
        }
    }
    // client 가 원하는 조각을 몇 개 만들 수 있는지 count 해준다.
    for (int i = 0; i <= client; i++)
        ans += (sizeA[i] * sizeB[client - i]);
 
    cout << ans << '\n';
}
 cs

[ github ]

https://github.com/travelbeeee/BOJ/blob/master/BOJ2632.cpp

 

travelbeeee/BOJ

백준 문제풀이. Contribute to travelbeeee/BOJ development by creating an account on GitHub.

github.com

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 9881 : Ski Course Design  (0) 2020.08.25
[BOJ] 13711 : LCS 4  (0) 2020.08.25
[BOJ] 11964 : Fruit Feast  (0) 2020.08.23
[BOJ] 18808 : 스티커 붙이기  (0) 2020.08.23
[BOJ] 10282 : Failing Components  (0) 2020.08.21

문제 : https://www.acmicpc.net/problem/11964

BFS 그래프탐색

[ 문제풀이 ]

 레몬과 오렌지를 먹어서 배부름 정도를 최대로 만들고 싶은데, 이때 물을 중간에 한 번 먹어서 배부름 정도를 절반으로 낮출 수 있다. 레몬과 오렌지의 배부름 정도는 A, B이고 내 최대 배부름은 T이므로 T를 넘지 않는 선에서 레몬과 오렌지를 먹어 만들 수 있는 최대 배부름을 구하자.

 

[ 알고리즘풀이 ]

 ( 배부름 정도, 물을 먹었는지 ) 2개의 값을 가지고 ( 0, 0) 에서 시작해서 BFS 탐색을 진행하면 된다.

 

[ 코드 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
#include<iostream>
#include<queue>
#include<algorithm>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int T, A, B, ans = -1;
    bool visited[500001][2] = {};
 
    cin >> T >> A >> B;
 
    queue<pair<int, bool>> q;
    q.push({ 0, 0 });
    visited[0][0] = 1;
    while (!q.empty()) {
        int curF = q.front().first;
        bool drinkWater = q.front().second;
        q.pop();
 
        ans = max(ans, curF);
 
        if (curF + A <= T && !visited[curF + A][drinkWater]) {
            q.push({ curF + A, drinkWater });
            visited[curF + A][drinkWater] = 1;
        }
        if (curF + B <= T && !visited[curF + B][drinkWater]) {
            q.push({ curF + B, drinkWater });
            visited[curF + B][drinkWater] = 1;
        }
        if (!drinkWater && !visited[curF / 2][!drinkWater]) {
            q.push({ curF / 2, !drinkWater });
            visited[curF / 2][!drinkWater] = 1;
        }
    }
    cout << ans << '\n';
 
    return 0;
}
 cs

[ gitHub ]

https://github.com/travelbeeee/BOJ/blob/master/BOJ11964.cpp

 

travelbeeee/BOJ

백준 문제풀이. Contribute to travelbeeee/BOJ development by creating an account on GitHub.

github.com

 

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 13711 : LCS 4  (0) 2020.08.25
[BOJ] 2632 : 피자판매  (0) 2020.08.24
[BOJ] 18808 : 스티커 붙이기  (0) 2020.08.23
[BOJ] 10282 : Failing Components  (0) 2020.08.21
[BOJ] 2517 : 달리기  (0) 2020.08.14

+ Recent posts

티스토리툴바