문제
https://www.acmicpc.net/problem/2217
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
Integer[] ropes = new Integer[N];
for (int i = 0; i < N; i++) {
ropes[i] = Integer.parseInt(bf.readLine());
}
Arrays.sort(ropes, Collections.reverseOrder());
int result = 0;
for (int i = 0; i < N; i++) {
int sub = ropes[0] - ropes[i];
int weight = (ropes[0] - sub) * (i + 1);
if (result < weight) {
result = weight;
}
}
System.out.println(result);
}
}
풀이 방법
- 줄이 버틸 수 있는 최대 중량을 입력받은 후, 내림차순으로 정렬한다.
- 내림차순으로 정렬했을 때 첫번째 값이 최대 중량이 가장 큰 줄이다. 이 무게는 곧, 줄 하나가 버틸 수 있는 최대 중량이 된다.
- 이를 이용해서 로프들을 순회하며
(최대 로프 중량 - 현재 로프 중량과의 차이) * 로프의 개수연산을 수행한다.💡예를 들어 입력이15, 10이라면?- 한 줄이 버틸 수 있는 최대 중량이 15kg이다.
- 풀어서 설명하면 최소한 15kg 이상의 중량을 버틸 수 있으며, 이것의 줄 한 개 중량의 최대치가 된다.
- 15kg줄 다음에는 10kg줄이 존재한다. 여기서
최대 로프 중량(15) - 현재 로프 중량과의 차이(5)가 15kg 줄과 10kg 줄 두 개를 사용했을 때 견딜 수 있는 줄 하나의 최대 중량이 된다.
- 따라서
(15 - 5)* 2 = 20이 총 견딜 수 있는 중량이 된다.
핵심 포인트
- 이 문제의 경우 입력이 크기 때문에
O(n)안에 해결해야 한다.
- 가장 큰 중량을 견딜 수 있는 로프가 기준점이 된다는 것을 파악해야 한다.
int weight = (ropes[0] - sub) * (i + 1);이 수식을 생각할 수 있어야 한다.
보완할 점 / 느낀 점
- 처음 문제에 접근할 때는, 입력으로 들어온 수의 모든 약수를 구해서 최대 중량을 구하려고 했다.
→ 이렇게 구현할 경우, 구현도 복잡하고 특히 시간 초과나 메모리 초과가 날게 뻔했다.
- 생각을 바꿔서
줄을 자른다.라는 개념으로 접근하였다. 이러한 접근으로 통해 위 수식을 도출하였다.
- 수식을 도출한 후 적용했을 떄 답은 맞게 나왔으나, 이중 for문을 사용하여 메모리 초과가 발생하였다.
- 여기서 키포인트는 이중 for문을 통해 모든 줄에 대해서 나머지 줄들의 중량을 구할 필요 없이, 최대 중량 로프를 기준점 삼아서 한번의 for문으로 사용하는 줄의 종류에 따른 최대 중량을 구할 수 있다는 것이다.
- 이런 문제의 경우, 그림을 그려서 풀었다면 더 빨리 풀었을 것 같다. 바로 코드부터 작성하는 습관을 버려야 될 것 같다. 이 문제의 경우, 실버4치곤 조금 어려운 느낌이 있었다.
참고자료
- 시간복잡도 관련 질문글 : https://www.acmicpc.net/board/view/91157