안녕하세요!
35번째 문제입니다.
이번 글 역시 푸는 방식은 동일합니다!
1. 문제선택 및 설명
2. 문제접근 (알고리즘)
3. 문제풀기 (코딩하기)
4. 성공 (실패 시 2번)
1. 문제선택
이번 문제도 백준에 있는 문제입니다.
https://www.acmicpc.net/problem/2217 - 문제링크
문제설명 - 로프
문제
주어진 문제는 N개의 로프가 있고, 각 로프는 그 굵기나 길이가 달라서 들 수 있는 중량이 서로 다를 수 있다. 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다.
예를 들어, k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각 로프에는 w/k만큼의 중량이 걸리게 된다. 주어진 로프들 중 일부 또는 전체를 사용하여 들어올릴 수 있는 물체의 최대 중량을 구하는 프로그램을 작성해야 한다. 이때 모든 로프를 반드시 사용할 필요는 없으며, 최적의 로프 조합을 찾아서 최대 중량을 계산해야 한다.
입력
첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.
출력
첫째 줄에 답을 출력한다.
즉, 로프의 수를 입력 후, 로프가 견딜 수 있는 무게를 입력합니다.
로프를 다 사용할 필요는 없지만, 주어진 로프 속에서 가장 최적의 무게를 구하는 문제입니다.
예를 들어, 로프의 수는 5개이고, 각각 1, 2, 4, 6, 8 kg의 무게를 견딜 수 있습니다.
그러면 총 5개의 경우의 수를 볼 수 있는데,
1kg을 선택한다면 모든 로프에 해당이 되기 때문에 5를 해서 총 5kg의 무게를 버틸 수 있습니다.
이런식으로
2kg - 24 = 8
4kg - 43 = 12
6kg - 62 = 12
8kg - 8*1 = 8
따라서 총 12kg가 최대로 버틸 수 있는 문제입니다.
2. 문제접근 (알고리즘)
a. 로프의 수 입력받음
b. 로프의 수 만큼 무게 입력받음
c. 무게별로 자신보다 크거나 같은 수 만큼 곱함.
d. 곱한 값중 가장 큰 값을 출력
4. 문제풀기
(코딩하고 오겠습니다...) - 14분
#include <stdio.h>
#include <stdlib.h>
// 비교 함수
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int main(void) {
int n;
scanf("%d", &n);
int weight[n];
for(int i = 0; i < n; i++) {
scanf("%d", &weight[i]);
}
qsort(weight, n, sizeof(int), compare);
int heaviest = 0;
// 각 로프를 사용할 때 최대 중량 계산
for(int i = 0; i < n; i++) {
int total = weight[i] * (n - i); //이미 정렬이 되어 있기 때문에, i만큼 빼서 곱함
if (heaviest < total) {
heaviest = total;
}
}
printf("%d\n", heaviest);
return 0;
}최종 결과입니다.
바뀐점이 있다면 무게를 입력받은 이후 qsort로 정렬을 해줬습니다.
그렇게 하면 무게가 랜덤으로 입력받아도 순서대로 나열이 되기 때문에, 최종 무게를 구할 때 로프의 숫자 - 자신 위치를 뺀 값을 곱하면 제일 큰 무게를 구할 수 있습니다.
한번 틀리고 한번 시간초과 이후 통과됐습니다.
https://github.com/hjalope
제 깃헙링크입니다:)
감사합니다!
