으... 월..요..일..좋...아...(아님)
주말이 지나고 새로운 평일이 시작되었다.
그런데 난 월요일이 가장 기운이 빠진다.
(공강인데 왜그럴까??)
그래도 이 게으름을 이기고 드디어... 노트북 앞에 앉았다.
오늘도 블로그써야지!!
문제
https://www.acmicpc.net/problem/2217
2217번: 로프
N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하
www.acmicpc.net
오늘의 문제를 보아하니 음?? 뭔소리지?
문제가 무슨 뜻인지 모르겠다....
로프는 임의로 몇개를 골라 사용할 수 있고, 각 로프에는 고르게 중량이 걸리게 되니까
예제 입력1에서 확인해보자.
10이랑 15가 있는데,
만약 10인 로프만 사용하게 되면 최대 중량은 10이다.
15인 로프만 사용하게 된다면? 최대 중량은 15가 될 것이다.
그러면 만약 10, 15 로프를 둘 다 사용한다면? 두 로프에는 고르게 중량이 걸리게 되니까 10+10 해서 20이 최대 중량이 되는 것이다.
=> 그래서 최대 중량은 20이 되는 것이다.
음.. 이렇게 정리하니까 알겠다.
그러면 문제를 풀려면 경우의 수를 생각하여 하나하나 비교해서 최댓값을 구해야할 것 같다. 일단 10보다는 15가 더 큰 중량을 들 수 있으니까 내림차순으로 정렬해줘야겠다. 고른 로프 중 가장 작은 중량량을 들 수 있는 로프에 고른 로프의 수를 곱하면 최대 중량이 나온다. (즉, 고른 로프의 수x고른 로프 중 최소 중량)
이렇게 생각을 해봤으니 이제 코드를 작성하자!
// 틀린 코드
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int r[10000]; //로프
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> r[i];
}
int max_r = 0;//최대 중량 (결과)
int min, max;
sort(r, r + n, greater<int>()); //내림차순으로 정렬
for (int i = 1; i <= n; i++) {//고른 개수
for (int j = 0; j < i; j++) {//로프들
min = r[j];
if (min>r[j]) {
min = r[j]; //고른 것 중 가장 작은 로프
}
}
max = min * i;//최대 중량
if (max_r < max) {
max_r = max;
}
}
cout << max_r << endl;
return 0;
}
아.. 인덱스를 j로 써야하는데 i로 써서 에러나서 고치고 예제 입력을 넣어보니 잘 출력되길래 제출해봤더니...
이번에는 런타임에러 ㅎㅎ
하지만 괜찮다... 틀렸다는 것은 배울 수 있는 기회가 생겼다는 것...(자기 최면)
후후훗 즐.겁.다.
벡터로 바꿔서 푸니까 이번엔 시간초과가 됐다...아무래도 배열로 해야될 것 같다.
모르겠다...아무리봐도 할당된 곳을 넘어간 건 없는 것 같은데...ㅠㅠ
다른 풀이를 한번 찾아봐야겠다.
아참! 내 풀이는 별을 삼각형 모양으로 출력하는 방법을 이용해서 풀었다...(어차피 런타임에러가 났지만...)
https://m.blog.naver.com/gta3g/220507023540
+ 추가) 이럴 수가... 다른 풀이를 보고 내가 다시 코드를 작성해보며 틀린 이유를 알아버렸다.
진짜 멍청한 실수를 저지르다니!!!
나는 입력에 이렇게 써있길래
첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.
로프를 입력받는 배열의 크기를 10,000로 정해주었다(r[10000]).
그런데!! 문제에서는 이렇게 되어있는 것이다!!
N(1 ≤ N ≤ 100,000)개의 로프가 있다.
이럴 수가... 입력에 나와있는 10,000이라는 값은 최대 중량을 말하는 거였는데, 대충 읽어서 N에 대한 설명인줄 알았던 것이다...
오늘의 교훈...
문제는 잘 읽자.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int r[100000]; //로프
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> r[i];
}
int max_r = 0;//최대 중량 (결과)
int min, max;
sort(r, r + n, greater<int>()); //내림차순으로 정렬
for (int i = 1; i <= n; i++) {//고른 개수
for (int j = 0; j < i; j++) {//로프들
min = r[j];
if (min > r[j]) {
min = r[j]; //고른 것 중 가장 작은 로프
}
}
max = min * i;//최대 중량
if (max_r < max) {
max_r = max;
}
}
cout << max_r << endl;
return 0;
}
그래서~~ 이렇게 r[100000] 고쳐주면~~~
정답~~~~(짝짝)
다른 분들 풀이
#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;
}
출처: https://beginnerdeveloper-lit.tistory.com/36 [초보 개발자의 이야기, 릿허브:티스토리]
내림차순으로 할 필요없이 그냥 오름차순으로 정렬하여 최댓값을 중량이 가장 큰 로프 하나만 이용했을 때(인덱스: N-1)로 초기화해주셨다. 그리고 큰 것부터 차례대로 해야하니까 N-1부터 0까지 반복문을 돌려주셨다. 나는 여기서 개수를 곱해주기 위해 이중 반복문을 사용했는데 저런 식으로 코드를 작성하여 N-i를 곱해준 것을 보고 놀랐다.
게다가 어차피 고르게 중량이 걸리니까 고른 로프 중에서 가장 작은 로프를 찾을 필요 없이 하나의 반복문을 통해 인덱스가 i인 로프에 개수를 곱해주면 되는 거였다!!
이렇게 쉽게 풀 수 있다니... 난 너무 복잡게 생각한 것 같다.
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
int rope[100001];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
for (int i = 0; i < N; i++)
cin >> rope[i];
sort(rope, rope + N, greater<int>());
long long result = 0;
for (int i = 0; i < N; i++) {
long long sum = rope[i] * (i + 1);
if(sum > result)
result = sum;
}
cout << result;
return 0;
}
출처: https://penglog.tistory.com/113
이 분은 나처럼 내림차순으로 하셨다. 그리고 나와는 다르게 이 분도 위에 오름차순으로 했던 분처럼 반복문을 하나만 사용하여 코드를 작성하셨다. 반복문을 어떻게 사용하느냐에 따라 코드가 길어지기도 짧아지기도 한다. 난 아직 문제를 많이 풀어봐야할 것 같다. 그래야 어떻게 작성하는 것이 더 효율적인지 알 수 있을 것 같다.
'백준 > C++' 카테고리의 다른 글
[C++] 백준 3273 두 수의 합 (4) | 2023.12.06 |
---|---|
[C++] 백준 2751번 수 정렬하기 2 (2) | 2023.12.05 |
[C++] 백준 1764번 듣보잡 (2) | 2023.12.03 |
[C++] 백준 1302번 베스트셀러 (2) | 2023.12.02 |
[C++] 백준 1181번 단어 정렬 (2) | 2023.12.01 |