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

 

2352번: 반도체 설계

첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

www.acmicpc.net

1번 포트부터 n번 포트까지 연결이 꼬이지 않게 최대로 연결해야 하는 문제로 최장 증가수열문제이다.

 

 

12015번 가장 긴 증가하는 부분 수열 2 문제(문제 링크)와 똑같은 코드로 nlogn만에 풀 수 있다.

(12015번 문제 풀이 링크)

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int n;
vector<int> vt;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    vt.push_back(0);
 
 
 
    int num;
    for (int i = 0; i < n; i++) {
        cin >> num;
        if (num > vt.back()) {
            //벡터의 가장 마지막 값보다 크다면(증가하는 순서) push
            vt.push_back(num);
        }
        else {
            //num이상의 값이 처음으로 나타나는 위치에 num을 넣는다.
            int index = lower_bound(vt.begin(), vt.end(), num) - vt.begin();
            vt[index] = num;
        }
    }
 
 
 
    //처음에 넣어놓은 0을 제외한 벡터의 사이즈가 최장 증가 수열의 길이
    cout << vt.size() - 1 << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17837. 새로운 게임 2  (0) 2020.02.03
[BOJ] 1600. 말이 되고픈 원숭이  (0) 2020.02.01
[BOJ] 12783. 가장 긴 증가하는 부분 수열 3  (0) 2020.01.29
[BOJ] 12015. 가장 긴 증가하는 부분 수열 2  (0) 2020.01.29
[BOJ] 1965. 상자넣기  (0) 2020.01.29

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

 

12738번: 가장 긴 증가하는 부분 수열 3

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

www.acmicpc.net

12015번 가장 긴 증가하는 부분 수열 2 문제(문제 링크)와 거의 똑같은 LIS 문제이다. (12015번 문제 풀이 링크)

 

 

 

두 문제의 차이는 수열의 값의 범위뿐이다. 이번 문제에서는 범위가 (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) 으로 처음에 벡터에 넣어놓는 값으로 -1,000,000,000보다 작은 값을 넣어놓기만 하면 된다.

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int n;
vector<int> vt;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    vt.push_back(-2000000000);
 
 
 
    int num;
    for (int i = 0; i < n; i++) {
        cin >> num;
        if (num > vt.back()) {
            //벡터의 가장 마지막 값보다 크다면(증가하는 순서) push
            vt.push_back(num);
        }
        else {
            //num이상의 값이 처음으로 나타나는 위치에 num을 넣는다.
            int index = lower_bound(vt.begin(), vt.end(), num) - vt.begin();
            vt[index] = num;
        }
    }
 
 
 
    //처음에 넣어놓은 0을 제외한 벡터의 사이즈가 최장 증가 수열의 길이
    cout << vt.size() - 1 << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1600. 말이 되고픈 원숭이  (0) 2020.02.01
[BOJ] 2532. 반도체 설계  (0) 2020.01.29
[BOJ] 12015. 가장 긴 증가하는 부분 수열 2  (0) 2020.01.29
[BOJ] 1965. 상자넣기  (0) 2020.01.29
[BOJ] 11053. 가장 긴 증가하는 부분 수열  (0) 2020.01.29

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

 

12015번: 가장 긴 증가하는 부분 수열 2

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

www.acmicpc.net

LIS 문제이지만 11053번 가장 긴증가하는 부분 수열문제처럼 dp로 풀 수 없다.

dp로 풀면 시간 복잡도가 n제곱이 나오는데 이 문제는 n의 최댓값이 1,000,000이므로 n제곱으로 풀면 시간초과가 난다.

 

 

이분 탐색을 이용하여 nlogn만에 풀 수 있다.

 

 

0. 우선 입력으로 들어오는 최솟값보다 작은 값을 벡터에 넣어놓고 시작한다.

 

 

1. 값을 입력 받는다.

- 벡터의 맨 마지막 값보다 크다면(증가하는 순서라면) 입력받은 값을 벡터에 넣는다.

- 그렇지 않다면 이분탐색으로 벡터에 입력받은 값 이상의 값이 처음으로 나타나는 위치에 입력받은 값을 넣어준다.

(lower_bound를 이용하여 쉽게 구할 수 있다. )

 

 

2. 입력이 끝나면 벡터의 사이즈 -1한 값이 가장 긴 증가하는 부분 수열의 길이가 된다.

(처음에 넣어 놓은 값을 제외하기 위해 1을 뺀다)

 

 

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int n;
vector<int> vt;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    vt.push_back(0);
 
 
 
    int num;
    for (int i = 0; i < n; i++) {
        cin >> num;
        if (num > vt.back()) {
            //벡터의 가장 마지막 값보다 크다면(증가하는 순서) push
            vt.push_back(num);
        }
        else {
            //num이상의 값이 처음으로 나타나는 위치에 num을 넣는다.
            int index = lower_bound(vt.begin(), vt.end(), num) - vt.begin();
            vt[index] = num;
        }
    }
 
 
 
    //처음에 넣어놓은 0을 제외한 벡터의 사이즈가 최장 증가 수열의 길이
    cout << vt.size() - 1 << '\n';
 
    return 0;
}
hColored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2532. 반도체 설계  (0) 2020.01.29
[BOJ] 12783. 가장 긴 증가하는 부분 수열 3  (0) 2020.01.29
[BOJ] 1965. 상자넣기  (0) 2020.01.29
[BOJ] 11053. 가장 긴 증가하는 부분 수열  (0) 2020.01.29
[BOJ] 2167. 2차원 배열의 합  (0) 2020.01.24

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

 

1965번: 상자넣기

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의

www.acmicpc.net

LIS (Longest increasing Subsequence) 최장 증가 수열 문제이다.

 

백준문제 중에 11053 가장 긴 증가하는 부분 수열 문제(문제 링크)와 똑같은 코드로 풀 수 있다. (문제 풀이 링크)

 

 

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
#include <iostream>
using namespace std;
 
int arr[1000];
int dp[1000];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
 
    for (int i = 0; i<n; i++) cin >> arr[i];
 
 
    for (int i = 0; i<n; i++) {
        //처음엔 자기 자신의 길이인 1
        dp[i] = 1;
 
        //i번보다 앞의 값들과 비교
        for (int j = 0; j<i; j++) {
 
            //j번째 값이 i 번째 값보다 작아야 하고
            //dp값이 현재 가진 값보다 같거나 커야한다.
            if (arr[j] < arr[i] && dp[j] >= dp[i]) {
                //현재 i번째 값이 부분 수열에 추가되므로 길이는 +1이 된다.
                dp[i] = dp[j] + 1;
            }
        }
    }
 
 
    //최댓값을 찾는다.
    int ans = 0;
    for (int i = 0; i<n; i++) {
        if (ans < dp[i]) ans = dp[i];
    }
 
    cout << ans << '\n';
 
    return 0;
}
 
Colored by Color Scripter
  

 

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 12783. 가장 긴 증가하는 부분 수열 3  (0) 2020.01.29
[BOJ] 12015. 가장 긴 증가하는 부분 수열 2  (0) 2020.01.29
[BOJ] 11053. 가장 긴 증가하는 부분 수열  (0) 2020.01.29
[BOJ] 2167. 2차원 배열의 합  (0) 2020.01.24
[BOJ] 2805. 나무 자르기  (0) 2020.01.21

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

 

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

www.acmicpc.net

문제 제목 그대로 가장 긴 증가하는 부분 수열 LIS (Longest increasing Subsequence) 문제이다.

일반적으로 dp 식을 사용해서 풀 수 있다.

 

 

 

dp[i]는 수열의 i번째 값을 마지막으로 하는 가장 긴 증가하는 부분 수열이다.

dp[i]값을 구하기 위해서는 첫 번째 값부터 i-1번째 값( j )까지를 검사한다. -> 시간 복잡도는 n제곱이 된다

(먼저 dp배열은 자기 자신을 부분 수열로 하면 최소 길이가 1이므로 1로 초기화해준다)

 

 

 

1. j번 수열의 값이 i번 수열의 값보다 작고 (증가하는 수열이어야 하므로)

2. dp[j]값은 현재 dp[i]값보다 같거나 커야 한다(가장 긴 수열)

위의 조건을 만족한다면 dp[i] 는 dp[j] + 1 값을 가지게 된다(수열의 길이가 1 늘어남) 

 

 

 

문제에 나온 예시를 그림으로 보면 처음에 첫 번째 값(i가 0)인 10은 최대 길이가 1이므로 1인 상태로 다음 수열로 넘어간다.

 

 

 

 

 

수열의 다음 값(i가 1)은 20인데 앞의 값은 10 밖에 없다. 10은 20보다 작고 dp값도 같기 때문에 dp[i]값은 +1 된다.

 

 

 

그다음 값은 10인데 앞의 값들(10과 20) 중 10보다 작은 값이 없으므로 길이는 그대로 자기 자신인 1이 된다.

 

그리고 i는 증가해서 30 값을 가리킨다. 현재 i가 3이므로 0번부터 2(i-1) 번까지의 값을 보면 된다.

0번부터 2번까지의 값은 각각 10, 20, 10으로 모두 30보다 작다.

이중 dp배열의 가장 큰 값+1이 dp[i]값이 되므로 dp[1]값인 2에서 1을 더한 3이 dp[3]에 저장된다.

 

 

 

 

 

i값이 4가 되고 이제 j는 0부터 3까지의 값을 검사한다.

이 중 20보다 작은 값은 0번째와 2번째이다. 둘 다 10이고 dp의 값도 1로 현재 dp[i]와 같으므로 dp[i]는 dp[j]에 1을 더한 값인 2가 된다.

 

 

 

 

 

마지막 값인 50과 앞의 값들을 비교해보면 모두 50보다 작다. 그러므로 가장 큰 dp값인 dp[3] + 1 한 값인 4가 dp[5]에 저장된다.

 

 

 

 

마지막 값이 작은 값인 경우에는 마지막 위치에 최댓값이 저장되지 않을 수 있으므로 dp배열을 모두 검사해서 최댓값을 찾아야 한다.

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
#include <iostream>
using namespace std;
 
int arr[1000];
int dp[1000];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
 
    for (int i = 0; i<n; i++) cin >> arr[i];
 
 
    for (int i = 0; i<n; i++) {
        //처음엔 자기 자신의 길이인 1
        dp[i] = 1;
 
        //i번보다 앞의 값들과 비교
        for (int j = 0; j<i; j++) {
 
            //j번째 값이 i 번째 값보다 작아야 하고
            //dp값이 현재 가진 값보다 같거나 커야한다.
            if (arr[j] < arr[i] && dp[j] >= dp[i]) {
                //현재 i번째 값이 부분 수열에 추가되므로 길이는 +1이 된다.
                dp[i] = dp[j] + 1;
            }
        }
    }
 
 
    //최댓값을 찾는다.
    int ans = 0;
    for (int i = 0; i<n; i++) {
        if (ans < dp[i]) ans = dp[i];
    }
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 12015. 가장 긴 증가하는 부분 수열 2  (0) 2020.01.29
[BOJ] 1965. 상자넣기  (0) 2020.01.29
[BOJ] 2167. 2차원 배열의 합  (0) 2020.01.24
[BOJ] 2805. 나무 자르기  (0) 2020.01.21
[BOJ] 1654. 랜선 자르기  (0) 2020.01.20

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

 

2167번: 2차원 배열의 합

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y).

www.acmicpc.net

 

dp[a][b] = (0,0)를 왼쪽 위 시작점으로 (a,b)을 오른쪽 아래 끝점으로 하는 사각형 모양 안에 있는 배열의 합

으로 생각하고 풀면되는 dp문제이다.

 

 

식을 세우면 다음과 같이 된다.

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]

 

 

위의 그림과 같이 dp[i][j] 는 분홍색 네모와 초록색 네모를 합한 값에서 두 네모가 겹쳐진 dp[i-1][j-1] 을 빼주고 (i, j)의 위치에 있는 값을 더해주면 된다.

 

 

모든 위치에서 dp값을 구해놨다면 이제 (i, j)부터 (x, y)까지의 합도 쉽게 구할 수 있다.

dp값을 구할 때와 비슷하게 dp[x][y] (x,y까지의 합)에서 (i,j) 바깥 부분인 분홍색 네모와 초록색 네모 부분을 빼주고 겹치는 부분을 한번 더해준다.

 

그럼 값은 dp[x][y] - dp[x-i][y] - dp[x][y-j] + dp[i-1][j-1] 으로 구할 수 있다.

 

 

 

문제에서 범위는 1부터 시작하므로 인덱스도 1부터 시작하도록 했다.

그러면 i 나 j 가 1 일 때 i-1 이나 j-1 이 되어도 인덱스가 0이 되므로 그냥 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
29
30
31
32
33
34
#include <iostream>
using namespace std;
 
int arr[301][301];
int dp[301][301];
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin >> arr[i][j];
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j];
        }
    }
 
    int k;
    cin >>k;
 
    int i, j, x, y;
    int ans;
    while(k--) {
        cin >> i >> j >> x >> y;
        ans = dp[x][y] - dp[i-1][y] - dp[x][j-1] + dp[i-1][j-1];
        cout << ans << '\n';
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1965. 상자넣기  (0) 2020.01.29
[BOJ] 11053. 가장 긴 증가하는 부분 수열  (0) 2020.01.29
[BOJ] 2805. 나무 자르기  (0) 2020.01.21
[BOJ] 1654. 랜선 자르기  (0) 2020.01.20
[BOJ] 10816. 숫자 카드 2  (0) 2020.01.20

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

 

2805번: 나무 자르기

문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따

www.acmicpc.net

랜선 자르기 문제와 비슷하게 parametric search문제이다.

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
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
66
67
#include <iostream>
#include <algorithm>
using namespace std;
 
int n, m;
long long ans;
long long namu[1000000];
 
void solve(int left, int right) {
 
    long long h = (left + right) / 2;
    long long len = 0;
 
 
    //절단기 높이를 h(mid값)로 했을때 가져갈 수 있는 나무길이(len)을 구한다.
//(각 나무에서 h만큼 자르고 남은 값을 더한다)
    for (int i = 0; i < n; i++) {
        if (namu[i] >= h) {
            len += (namu[i] - h);
        }
    }
 
    
    if (len > m) {
        if (left >= right) {
            //left가 right보다 같거나 커진 경우 이분탐색 중지하고 ans 값과 현재 h를 비교
            if (ans < h) ans = h;
            return;
        }
 
        //len이 가져가려는 길이m보다 크면 절단기 크기를 더 크게 해도 된다.
        solve(h + 1, right);
    }
    else if (len < m) {
        //len이 가져가려는 길이 m보다 작으면 절단기 크기h를 더 작게해야 한다.
        solve(left, h - 1);
    }
    else {
        //같은 경우에는 현재 절단기 크기와 비슷해서 최댓값을 저장
        if (ans < h) ans = h;
        return;
    }
 
 
}
 
 
int main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> namu[i];
    }
 
    //정렬
    sort(namu, namu + n);
 
    //left값은 0 right값은 나무 길이의 최대 값
    solve(0, namu[n - 1]);
 
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 11053. 가장 긴 증가하는 부분 수열  (0) 2020.01.29
[BOJ] 2167. 2차원 배열의 합  (0) 2020.01.24
[BOJ] 1654. 랜선 자르기  (0) 2020.01.20
[BOJ] 10816. 숫자 카드 2  (0) 2020.01.20
[BOJ] 5567. 결혼식  (0) 2019.11.13

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

 

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

www.acmicpc.net

parametric search를 이용해서 푸는 문제이다. parametric search는 답이 나올 수 있는 범위 안에서 이분 탐색을 통해 답을 구하는 방법이다.

 

 

이 문제에서 가장 작게 자르는 크기는 1이고, 가장 크게 자르는 경우는 랜선의 길이중 최대값이기 때문에 각각 left값과 right값이 된다.

 

 

mid값으로 자르는 경우마다 잘라지는 랜선의 개수를 구하고

그 개수가 n값 이상인 경우에는 size를 더 늘릴 수 있으므로 left를 mid +1로 옮겨준다.

반대로 n값 보다 작은 경우에는 현재 mid값으로 n개를 만들 수 없으므로 right를 mid -1 로 옮긴다.

 

 

이 문제에서 주의할 점은 랜선의 길이가 2의31승 -1보다 작은 값이므로 left와 right를 더했을때 int범위를 넘어갈 수 있기때문에 타입을 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <algorithm>
using namespace std;
 
int k, n;
int arr[10000];
 
long long getCount(long long size) {
    long long cnt = 0;
 
    //k개의 랜선을 size(mid)로 잘라서 나오는 개수를 더해준다. 
    for (int i = 0; i < k; i++) {
        cnt += (arr[i] / size);
    }
 
    return cnt;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> k >> n;
    for (int i = 0; i < k; i++) cin >> arr[i];
 
    //입력 받은 랜선길이를 정렬한다.
    sort(arr, arr + k);
 
    int ans;
 
    //자를 수 있는 가장 작은 단위인 1이 left값
    long long left = 1;
    //자를 수 있는 가장 큰 단위(최댓값)인 arr의 마지막 값이 right 
    long long right = arr[k - 1];
 
 
 
    //이분 탐색
    while (left <= right) {
 
        long long mid = (left + right) / 2;
 
        //mid값으로 잘랐을때 나오는 랜선의 개수를 구한다
        long long cnt = getCount(mid);
 
        //mid값으로 잘라서 나온 랜선의 개수가 n이상이면 더 큰 값으로 잘라도 되므로 left값이 앞으로 간다.
        //현재 최대 길이는 mid값 만큼 자른 경우
        if (cnt >= n) {
            left = mid + 1;
            ans = mid;
        }
        else {
            //현재 mid값으로 랜선을 자르면 n개를 못만드는 경우
            //크기르 줄이기 위해 right를 mid앞쪽으로 당긴다.
            right = mid - 1;
        }
    }
 
    cout << ans << '\n';
 
 
 
    return 0;
}
Colored by Color Scripter
  

 

 

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2167. 2차원 배열의 합  (0) 2020.01.24
[BOJ] 2805. 나무 자르기  (0) 2020.01.21
[BOJ] 10816. 숫자 카드 2  (0) 2020.01.20
[BOJ] 5567. 결혼식  (0) 2019.11.13
[BOJ] 7662. 이중 우선순위 큐  (0) 2019.11.13

+ Recent posts

티스토리툴바