https://www.acmicpc.net/problem/1654 풀이: 배열을 받아온다. 배열의 들어있는 랜선의 길이 중 최댓값이 만들 수 있는 최대 길이의 랜선이므로 최댓값을 설정한다. 최솟값은 1로 설정한다. 최댓값과 최솟값의 중간값을 m이라고 하자. 모든 배열의 원소를 m으로 나눈 몫을 모두 더한다. 더한 값이 필요한 랜선의 갯수보다 작다면, m값이 너무 크다는 것이므로 최댓값을 m - 1 로 바꿔준다. 더한 값이 필요한 랜선의 갯수보다 크거나 같다면, 만들 수 있다는 것이므로 답에 저장해 놓는다. 이때, 랜선의 최대 길이를 찾아야 하므로, 랜선의 갯수와 같다고 바로 끝내지 말고 위로 가면서 최댓값을 찾아야한다.

https://www.acmicpc.net/problem/1655 풀이: 하나씩 숫자를 받아온다. 첫번째 숫자를 mid 라고 할 때, 현재 숫자가 mid보다 크거나 같다면, 배열 r 에 작다면, 배열 l 에 저장한다. mid를 배열 r 에 넣고, 배열 l 의 값 중 가장 큰 값으로 바꾼다. 만약, 배열 r과 l의 사이즈 차이가 2이상 난다면, mid값을 조정해준다. cout, cin 을 사용하면, 시간초과가 나므로 주의하자. 코드: 사용언어 : 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 #include <iostream>#include <queue>using namespace std; int n, m, mid; int main() { priority_queue<int, vector<int>, greater<int>> r; priority_queue<int> l; scanf("%d %d", &n, &mid); printf("%d\n", mid); while (--n) { scanf("%d", &m); m < mid ?

https://www.acmicpc.net/problem/2110 풀이: [백준]1654 랜선 자르기 참고 최대 거리를 설정하고, 그 거리를 기준으로 공유기를 설치할 수 있는지 확인하고, 이분탐색으로 최대 거리를 조절해 나간다. 코드: 사용언어 : 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 #include <iostream>#include <algorithm>using namespace std; long long n, k, i, a[200001], sum, m, l = 1, r, c = 0, d; int main() { cin >> k >> n; for (i = 0; i < k; i++) cin >> a[i]; sort(a, a + k); r = a[k - 1]; while (l <= r) { sum = 1; m = (r + l) / 2; d = a[0]; for (i = 1; i < k; i++) if (d + m <= a[i]) { d = a[i]; sum++; } if (sum < n) r = m - 1; else { c = max(c, m); l = m + 1; } } cout << c << endl; return 0; }

https://www.acmicpc.net/problem/2805 풀이: [백준]1654 랜선 자르기 참고 m값이 배열의 값보다 작은데 a[i] - m을 할 경우 -값이 나오므로 주의하자. 코드: 사용언어 : 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 #include <iostream>#include <algorithm>using namespace std; long long n, k, i, a[1000001], sum, m, l = 1, r = 0, c = 0; int main() { cin >> k >> n; for (i = 0; i < k; i++) { cin >> a[i]; r = max(r, a[i]); } while (l <= r) { sum = 0; m = (r + l) / 2; for (i = 0; i < k; i++) sum += a[i] < m ?

https://www.acmicpc.net/problem/1300 풀이: [백준]1654 랜선 자르기 참고 현재 숫자의 순서가 k를 넘어간다면, 오른쪽 탐색을, 아니라면 왼쪽으로 탐색한다. int형 사이즈를 넘어가니 long long으로 바꿔주자. 코드: 사용언어 : c++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <iostream>#include <algorithm>using namespace std; long long n, k, i, sum, m, l = 1, r, c; int main() { cin >> n >> k; r = n * n; c = r; while (l <= r) { sum = 0; m = (r + l) / 2; for (i = 1; i <= n; i++) sum += min(n, m / i); if (sum < k) l = m + 1; else { c = min(c, m); r = m - 1; } } cout << c << '\n'; }

https://programmers.co.kr 문제: 크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다. 예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x 2 = 30번의 곱하기 연산을 해야 합니다. 행렬이 2개일 때는 연산 횟수가 일정 하지만, 행렬의 개수가 3개 이상일 때는 연산의 순서에 따라서 곱하기 연산의 횟수가 바뀔 수 있습니다.