알고리즘 재활 6일차 - 백준 2217, 13305, 1541번

이틀 안썼다고 귀찮다니

초등학생이 된 기분

 

 

 

로프

 

 

 

 

그리디가 풀고 싶어 하나 더 풀었던 문제,

로프 수 만큼 병렬적으로 무게를 감당하고 이 로프들로 최대 중량을 구해내는 코드를 작성하면 된다.

간단하게 로프 길이가 긴 순서로 정렬하고, 가장 낮은 길이를 기준으로  로프 * 인덱스로 업데이트 해줬다.

 

import java.io.*;
import java.util.*;
 
public class Main { // S4 로프
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int maxWeight = 0;
        Integer[] nums = new Integer[N];
 
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(nums, Collections.reverseOrder());
 
        for (int i = 0; i < N; i++) {
            maxWeight = Math.max(maxWeight, nums[i] * (i + 1));
        }
 
        System.out.println(maxWeight);
    }
}
 

---

주유소

 

 

문제를 처음에 잘못 읽어서 좀 걸렸다

정리하면 가스의 가격이 인근보다 싸다면 다른 지역에 넘어가는 거리의 가스까지 미리 구입해야 한다.

1.  현재 지점에서 다음 지역까지 넘어갈 가스가 없다면 현재 지역에서 구매.
   
   1. 다음 지역의 가스 가격들을 비교해서 현재보다 낮은 가격이 나오기 전까지 거리의 가스를 미리 구입
2. 이동

import java.io.*;
import java.util.*;
 
public class Main { // S3 주유소
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] distance = new int[N - 1];
        int[] cost = new int[N];
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int j = 0; j < N - 1; j++) {
            distance[j] = Integer.parseInt(st.nextToken());
        }
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cost[i] = Integer.parseInt(st.nextToken());
        }
 
        long answer = 0;
        long minCost = cost[0];
 
        for (int i = 0; i < N - 1; i++) {
            if (cost[i] < minCost) {
                minCost = cost[i];
            }
            answer += minCost * distance[i];
        }
 
        System.out.println(answer);
    }
}
 

---

회의실 배정 

 

 

겹치지 않고 효율적이게 회의실을 사용해야 한다.

정렬은 필수적이겠고 그리디한 방식을 생각해야 했다.

시작시간으로 정렬하는 것도 중요하지만 끝나는 시간으로 정렬해야 보다 더 효율적으로 사용할 수 있다고

판단했다.

끝나는 동시에 바로 다음 회의를 쓸 수 있는 것도 고려해 주면 꿋

 

        Arrays.sort(nums,(o1,o2) -> {
            if(o1[1] == o2[1]){
                return o1[0] - o2[0];
            }
            return o1[1] - o2[1];
        });

을 통해서 오버라이딩 해줬고 시작시간이 같으면 끝나는 시간순으로 정렬해 줬다.

 

 

import java.io.*;
import java.util.*;
 
public class Main { // S1 회의실 배정
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int answer = 0;
 
        int [][] nums = new int[N][2];
 
        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            nums[i][0] = a;
            nums[i][1] = b;
        }
 
        Arrays.sort(nums,(o1,o2) -> {
            if(o1[1] == o2[1]){
                return o1[0] - o2[0];
            }
            return o1[1] - o2[1];
        });
 
        int now = 0;
 
        for(int i = 0; i<N; i++) {
            if (now <= nums[i][0]) {
                now = nums[i][1];
                answer++;
            }
        }
 
        System.out.println(answer);
 
    }
}