2217번: 로프
N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하
www.acmicpc.net
단순하게 생각했을때 쉽다고 생각되었다. N개의 로프중 최대중량이 가장 작은 로프가 항상 기준이 되어야한다
그렇지않으면 끊어지기 때문이다. 하지만
모든 로프를 사용해야할 필요는 없고, 임의로 몇 개의 로프를 골라서 사용해도 된다 라는 점을 생각해보았을때
1. N값을 입력받는다. N이 5이라면
2. 10, 15, 1, 18, 20 순으로 들어왔다고 치자
3. 모든 로프를 사용할 경우 1을 기준으로 5개의 로프는 5중량을 버틸 수 있다.
4. 위의 케이스는 극단적이지만 이 문제의 맹점이라고 생각한다. 이때 로프 1이 끼게 됨으로써 최대중량이 줄어들게된다 이 것을 구현하기 위해서는 내림차순으로 정렬을 한 후에 반복문을 통해 구할 수 있을거라 생각하고 구현해보겠습니당.net/problem/2217
2217번: 로프
N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하
www.acmicpc.net

단순하게 생각했을때 쉽다고 생각되었다. N개의 로프중 최대중량이 가장 작은 로프가 항상 기준이 되어야한다
그렇지않으면 끊어지기 때문이다. 하지만
모든 로프를 사용해야할 필요는 없고, 임의로 몇 개의 로프를 골라서 사용해도 된다 라는 점을 생각해보았을때
1. N값을 입력받는다. N이 5이라면
2. 10, 15, 1, 18, 20 순으로 들어왔다고 치자
3. 모든 로프를 사용할 경우 1을 기준으로 5개의 로프는 5중량을 버틸 수 있다.
4. 위의 케이스는 극단적이지만 이 문제의 맹점이라고 생각한다. 이때 로프 1이 끼게 됨으로써 최대중량이 줄어들게된다 이 것을 구현하기 위해서는 내림차순으로 정렬을 한 후에 반복문을 통해 구할 수 있을거라 생각하고 구현해보겠습니당
package test;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Integer[] rope = new Integer[n];
//로프의 중량을 담을 배열
for(int i=0;i<5;i++) {
rope[i]=sc.nextInt();
//중량 입력
}
Arrays.sort(rope,Collections.reverseOrder());
//내림차순 정렬
int[] wei = new int[n];
//최대중량을 담을 배열 선언
int result = 0;
//최대중량을 담을 변수
for(int i=0;;i++) {
if(i==0) {
wei[i] = rope[i];
//첫번째 바퀴때는 최대중량이 곧 로프의 최대중량이된다.
}
else {
//두번째 바퀴부터
if(wei[i-1] > (rope[i]+rope[i+1])/(i+2)) {
//만약 현재 최대중량보다 최대중량이 작다면
result = wei[i-1];
//result 변수에 현재 최대중량값을 저장한다.
break;
}
else {
wei[i] = (rope[i]+rope[i+1])/(i+2);
//그렇지 않다면 최대중량을 저장한다.
}
}
}
System.out.println(result);
}
}
단지 생각대로 적은 코드지만 돌아가지도 않고 뭔가 놓치고 있다 for에 else절이 이상한것 같다 다른 사람이 쓴 코드를 보며 내가 뭘 잘못했을까... 생각해봐야겟다
저녁밥을 먹으며 생각해보았다.
package test;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Integer[] rope = new Integer[n];
//로프의 중량을 담을 배열
for(int i=0;i<n;i++) {
rope[i]=sc.nextInt();
//중량 입력
}
Arrays.sort(rope,Collections.reverseOrder());
//내림차순 정렬
int max = 0;
for(int i =0; i<n;i++) {
if(max < rope[i] * (i+1)) {
max = rope[i] * (i+1);
}
}
System.out.println(max);
}
}
차근차근 생각해보니 쉬운문제였다
다른사람들의 코드는 오름차순으로 하는코드들을 봤는데
내림차순으로 정렬하는것이 미세하게나마 빠르다고 생각한다. 최대값을 구하는 것이기때문에
최대값을 찾은 후 뒤에나오는 값들은 무조건 최대값이 아니기때문에 계산할 필요가 없어진다.
'알고리즘 with 자바 > 그리디' 카테고리의 다른 글
| 백준 4796 : 캠핑 - JAVA (0) | 2021.03.18 |
|---|---|
| 백준 10162 : 전자레인지 - JAVA (0) | 2021.03.17 |
| 백준 1541 : 잃어버린 괄호 - JAVA (0) | 2021.03.16 |
| 백준 5585 : 거스름돈 - JAVA (0) | 2021.03.16 |
| 백준 11047 : 동전 0 - JAVA (0) | 2021.02.16 |
