[알고리즘] Greedy Algorithm | OJS 문제

컴퓨터알고리즘 OJS 과제 문제풀이입니다.

• 급료 계산
  사실 이거 망한것같다.. OJS는 통과했지만 백준은 통과하지못한 덜떨어진 코드.
  입력으로 1원 9개 5원 3개 10원 1개이고 최저임금이 7원이라하면 4명이 고용되어야하지만 나는 3명이 고용되지롱 ,,,
  1원과 5원의 조합을 생각하지 않아서 생기는 문제.
  일단 통과한 코드는 이렇다

  import java.util.*;
  
    public class G {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int employ = 0;
            int n = scanner.nextInt();
            int c = scanner.nextInt();
  
            int arr[][] = new int[n][2];
            for(int i = 0 ; i < n ; i++){
                arr[i][0] = scanner.nextInt();
                arr[i][1] = scanner.nextInt();
            }
  
            Arrays.sort(arr, new Comparator<int[]>(){
                @Override
                public int compare(int[] a, int[]b){
                    return Integer.compare(a[1], b[1]);
                }
            });
  
            for(int i = n-1 ; i >= 0 ; i--){
                while(true){
                    if(arr[i][1] == 0) break;
                    if(arr[i][0] >= c) {
                        arr[i][1]--;
                        employ++;
                    }
                    else {
                        if(arr[i][0]*arr[i][1] < c) break;
                        int coin = arr[i][0];
                        int cnt = 1;
                        while(coin < c) {
                            coin += arr[i][0];
                            cnt++;
                        }
                        arr[i][1] -= cnt;
                        employ++;
                    }
                }
            }
            System.out.println(employ);
        }
    }

• 회의실 배정
  나름 재미있는 문제였다.

  

  import java.util.*;
  
    class Time {
        int start;
        int end;
  
        public Time(int start, int end){
            this.start = start;
            this.end = end;
        }
  
        public int getStart() {
            return start;
        }
  
        public int getEnd() {
            return end;
        }
    }
    public class H {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
  
            Vector<Time> arr = new Vector<Time>();
            for (int i = 0 ; i < n ; i++) {
                int s = scanner.nextInt();
                int e = scanner.nextInt();
                arr.add(new Time(s, e));
            }
  
            Collections.sort(arr, new Comparator<Time>() {
                @Override
                public int compare(Time o1, Time o2) {
                    if (o1.getEnd() == o2.getEnd()) {
                        return o1.getStart() - o2.getStart();
                    }
                    else {
                    return o1.getEnd() - o2.getEnd();
                    }
                }
            });
  
            int cnt = 0;
            int e = -1;
  
            for(int i = 0 ; i < n ; i++){
                if(arr.get(i).getStart() >= e){
                    e = arr.get(i).getEnd();
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    }

• 신입사원
  서류순으로 정렬 후 면접점수만 돌면서 카운트 증가시켜주면 끝나는 문제였다.

  import java.util.*;
  
    class Grade {
        int document;
        int interview;
  
        public Grade (int document, int interview){
            this.document = document;
            this.interview = interview;
        }
  
        public int getDocument() {
            return document;
        }
  
        public int getInterview() {
            return interview;
        }
    }
  
    public class I {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int t = scanner.nextInt();
            for(int i = 0 ; i < t ; i++){
                Vector<Grade> grade = new Vector<Grade>();
                int n = scanner.nextInt();
                for(int j = 0 ; j < n ; j++){
                    int docu = scanner.nextInt();
                    int inter = scanner.nextInt();
                    grade.add(new Grade(docu, inter));
                }
  
                grade.sort((o1, o2) -> o1.document - o2.document);
  
                int cnt = 1;
                Grade start = grade.firstElement();
                for(Grade saram : grade){
                    if(saram.getInterview() < start.getInterview()){
                        start = saram;
                        cnt++;
                    }
                }
  
                System.out.println(cnt);
            }
        }
    }