일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 수학
- 브루트포스알고리즘
- C
- SQL
- 프로그래머스
- 그리디알고리즘
- 논문구현
- 이분탐색
- C언어
- 자료구조
- 정수론
- 해시를사용한집합과맵
- 프로그래머스코딩테스트
- Image Classification
- 백준
- 프로그래머스sql
- 문자열
- C++
- 정렬
- 프로그래머스연습문제
- 구현
- 큐
- 백준알고리즘
- 논문리뷰
- 다이나믹프로그래밍
- 사칙연산
- MySQL
- 이진탐색
- 그리디
- 소수판정
- Today
- Total
초보 개발자의 이야기, 릿허브
[C++] 백준 2217번 로프 본문
1. 문제이해
로프의 개수(N)와 각 로프가 버틸 수 있는 최대 중량이 주어진다.
로프를 이용해 중량이 W인 물체를 들어올리려고 할 때, 각 로프에는 동일한 중량이 걸리게 된다. (N / W)
로프중에서 몇 개만 뽑아서 사용하는 것이 가능할때,
들어올릴 수 있는 물체의 최대중량을 구하는 것이 목표이다.
2. 문제풀이
로프를 이용해 들 수 있는 물체의 최대중량을 구하는 문제이다.
언뜻 보면 간단해보이는 문제이지만, 두가지 조건이 있다.
1. 로프들 중 몇개만 뽑아서 사용하는 것이 가능하다.
2. 모든 로프에는 동일한 중량이 걸리게 된다.
위 두가지 조건을 고려하여 문제를 살펴보면 다음과 같다.
<예제 1>
문제의 예제에서는 최대중량이 10, 15인 로프 2개가 주어진다.
이를 이용해 물체를 들어올릴 수 있는 경우는 다음과 같다.
1. 15인 로프 하나만 사용한다면, 들어올릴 수 있는 최대 중량은 15
2. 10인 로프 하나만 사용한다면, 들어올릴 수 있는 최대 중량은 10
3. 10, 15인 로프를 두개 사용한다면, 들어올릴 수 있는 최대 중량은 10 + 10 = 20
따라서, 위 로프들을 이용해 들어올릴 수 있는 최대 중량은 20이다.
3의 경우 20이 나오는 이유는 2. 모든 로프에는 동일한 중량이 걸리게 된다.때문이다.
10, 15 중 더 작은 값은 10이고, 10을 넘은 값을 걸게 되면 최대 중량이 10인 로프는 끊어지게 된다.
따라서, 로프 N개를 사용할 경우에는 로프로 들 수 있는 최대 중량은 (해당 로프들 중 최소중량) x N이 된다.
<예제 2>
다른 예제를 하나 더 살펴보자.
최대 중량이 2, 10, 8, 5, 7 인 로프 5개가 주어졌을 경우이다.
중량이 큰 로프부터 꺼내어 보아야하기 때문에, 위 값들을 정렬하면 2, 5, 7, 8, 10 이 된다.
위 로프들 중 큰 값부터 차례대로 사용해 들어올리면, 들어올릴 수 있는 경우는 다음과 같다.
1. 10인 로프 하나만 사용한다면, 들어올릴 수 있는 최대 중량은 10 (10 x 1)
2. 10, 8인 로프를 두개 사용한다면, 들어올릴 수 있는 최대 중량은 8 + 8 = 16 (8 x 2)
3. 10, 8, 7인 로프를 세개 사용한다면, 들어올릴 수 있는 최대 중량은 7 + 7 + 7 = 21 (7 x 3)
4. 10, 8, 7, 5인 로프를 네개 사용한다면, 들어올릴 수 있는 최대 중량은 5 + 5 + 5 + 5 = 20 (5 x 4)
5. 10, 8, 7, 5, 2 인 로프를 다섯개 사용한다면,들어올릴 수 있는 최대 중량은 2 + 2 + 2 + 2 + 2 = 10 (2 x 5)
따라서, 위 로프들을 이용해 들어올릴 수 있는 최대 중량은 21이다.
중량이 큰 로프부터 꺼내어 보는 이유는 1. 로프들 중 몇개만 뽑아서 사용하는 것이 가능하다.때문이다.
중량이 큰 로프를 가지고 뽑아야, 들어올릴 수 있는 물체의 최대 중량이 더 커지게 된다.
(10, 2 두개의 로프로 최대 4인 물체를 드는 것과, 10, 8 두개의 로프로 최대 16인 물체를 드는 것의 차이)
따라서, 로프가 N개 주어졌을 때,
위와 같은 조건을 고려하여 들어올릴 수 있는 물체의 최대 중량을 구하는 방법은 다음과 같다.
1. 주어진 로프의 최대중량을 정렬
2. 로프의 중량이 큰 것부터 뽑아나가며 해당 경우의 값을 최댓값과 비교
3. 소스코드
#include <iostream>
#include <algorithm>
using namespace std;
int rope[100000];
int main() {
int N; // 로프의 개수
int current; // 현재 중량
int max; // 최대 중량
cin >> N;
for (int i = 0; i < N; i++) {
cin >> rope[i];
}
// 로프의 중량을 정렬
sort(rope, rope + N);
// 최댓값을 우선 중량이 가장 큰 로프 하나만 이용했을 때로 초기화
max = rope[N - 1];
for (int i = N - 1; i >= 0; i--) {
// 현재 로프의 중량 (해당 로프의 중량 * 몇 개 달았는지)
current = rope[i] * (N - i);
if (max < current) { // 최대 중량보다 현재 중량이 더 크다면
max = current; // 최대 중량을 현재 값으로 초기화
}
}
cout << max;
return 0;
}
2. 문제풀이 방법에서 도출해낸 그대로 코드를 구현했다.
로프의 개수와 각 로프의 중량을 입력받아 정렬한 후, 로프의 중량이 큰것부터 차례로 뽑아
해당 경우 들어올릴 수 있는 중량(current)과, 현재까지 들어올릴 수 있는 최대 중량(max)을 비교,
현재 들어올릴 수 있는 중량이 더 크다면 최대 중량을 초기화했다.
내가 이해하는데 오래걸린 문제라.. 오늘은 문제풀이 부분을 자세하게 써보았다.
내가 헷갈려했던 부분이나 이해가 잘 되지 않았던 부분을 자세하게 써보았는데,
혹여나 헤매고 계실 분들에게 많은 도움이 되었으면 좋겠다. 😊
'코딩테스트 > 📗 백준 (BOJ)' 카테고리의 다른 글
[C++] 백준 2485번 가로수 (1) | 2021.09.01 |
---|---|
[C++] 백준 20044번 Project Teams (0) | 2021.09.01 |
[C++] 백준 10845번 큐 (1) | 2021.08.28 |
[C++] 백준 20300번 서강근육맨 (0) | 2021.08.27 |
[C++] 백준 11508번 2+1 세일 (0) | 2021.08.26 |