[C++] 백준 2217번 로프

으... 월..요..일..좋...아...(아님)

주말이 지나고 새로운 평일이 시작되었다.

그런데 난 월요일이 가장 기운이 빠진다.

(공강인데 왜그럴까??)

 

그래도 이 게으름을 이기고 드디어... 노트북 앞에 앉았다.

오늘도 블로그써야지!!

 

문제

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

2217번: 로프

 

오늘의 문제를 보아하니 음?? 뭔소리지?

문제가 무슨 뜻인지 모르겠다....

 

로프는 임의로 몇개를 골라 사용할 수 있고, 각 로프에는 고르게 중량이 걸리게 되니까

예제 입력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

이 분은 나처럼 내림차순으로 하셨다. 그리고 나와는 다르게 이 분도 위에 오름차순으로 했던 분처럼 반복문을 하나만 사용하여 코드를 작성하셨다. 반복문을 어떻게 사용하느냐에 따라 코드가 길어지기도 짧아지기도 한다. 난 아직 문제를 많이 풀어봐야할 것 같다. 그래야 어떻게 작성하는 것이 더 효율적인지 알 수 있을 것 같다.