백준 :: 그리디

그리디

 

 

 

 

---

 

 

세탁소 사장 동혁

 

 

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int testCase = scanner.nextInt();

        int[] money  = new int[testCase];

        for (int i =  0; i < testCase; i++){

            money[i] = scanner.nextInt();

        }

        for (int i = 0; i < money.length; i++){

            int quater = money[i] / 25;

            money[i] = money[i] % 25;

            int dime = money[i] / 10;

            money[i] = money[i] % 10;

           

            int nickel = money[i] / 5;

            money[i] = money[i] % 5;

            int penny = money[i] / 1;

            money[i] = money[i] % 1;

       

            System.out.println(quater+ " "+dime+" "+nickel+" "+penny);

        }

    }

}

 

 

 

---

 

 

전자레인지

 

 

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int second = scanner.nextInt();

       

        int minutes5 = second / 300;

        second = second % 300;

        int minute = second / 60;

        second = second % 60;

       

        int seconds10 = second / 10;

        second = second % 10;

        if(second > 0){

            System.out.println("-1");

        } else {

            System.out.println(minutes5+ " "+minute+" "+seconds10);

        }

    }

}

 

 

---

거스름돈

 

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int pay = scanner.nextInt();

        int getMoney = 1000 - pay;

        int[] changes = {500, 100, 50, 10, 5, 1};

        int answer = 0;

        for(int i : changes){

            answer += getMoney / i;

            getMoney %= i;

        }

       

        System.out.println(answer);

    }

}

 

 

 

---

캠핑

 

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int number = 1;

       

        while(true){

            int L = scanner.nextInt();

            int P = scanner.nextInt();

            int V = scanner.nextInt();

            if(L==0 && P==0 && V==0){

                break;

            }

            int stay = (V / P) * L + Math.min(V % P, L);

            System.out.println("Case "+(number++)+": " + stay);

        }

    }

}

 

 

 

---

컵홀더

 

import java.io.*;

import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

       

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int people = Integer.parseInt(br.readLine());

        String[] seat = br.readLine().split("");

        int count = 1;

        for(int i = 0; i < people; i++){

            if(seat[i].equals("S")){

            count++;

            } else {

                i++;

                count++;

            }

        }

        System.out.println(Math.min(people, count));

    }

}

 

 

---

설탕배달

 

 

많이 고민했던 문제..!

다른 풀이 보고 해결했다.

 

1. 3과 5로 구성하지 못하는 수는 4와 7이다.
2. N이 5로 나누어 떨어지면 출력한다.
3. 나누어 떨어지지 않으면 N - 3
4. 반복한다.

 

 

import java.io.*;

import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

 

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int count = 0;

        while(true){

            if(N == 4 || N == 7){

                count = -1;

                break;

            } else if(N % 5 == 0){

                count += N / 5;

                break;

            } else {

                N -= 3;

                count++;

            }

        }

       

        System.out.println(count);

    }

}

 

 

 

---

ATM

 

 

import java.io.*;

import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

 

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] time = new int[N];

        for(int i = 0; i < N; i++){

            time[i] = Integer.parseInt(st.nextToken());

        }

        Arrays.sort(time);

       

        int answer = time[0];

        for(int i = 1; i < time.length; i++){

            time[i] = time[i] + time[i-1];

            answer += time[i];

        }

       

        System.out.println(answer);

    }

}

 

 

---

동전 0

 

 

for문을 큰 수부터 -로 내려가며 찾는다.

 

import java.io.*;

import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        int K = Integer.parseInt(st.nextToken());

        int[] money = new int[N];

        for(int i = 0; i < N; i++){

            money[i] = Integer.parseInt(br.readLine());

        }

        int count = 0;

        for(int i = N-1; i >= 0; i--){

            if(money[i] <= K){

                count += K / money[i];

                K = K % money[i];

            }

           

        }

        System.out.println(count);

    }

}

 

 

---

회의실 배정

 

 

이런 문제 이전에 풀어봐서 알고리즘 익숙했다!

다만 정렬 때문에 틀렸었음..!

 

import java.io.*;

import java.util.*;

public class Main2 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st;

        int[][] info = new int[N][2];

        for(int i = 0; i < N; i++){

            st =  new StringTokenizer(br.readLine());

            info[i][0] = Integer.parseInt(st.nextToken());

            info[i][1] = Integer.parseInt(st.nextToken());

        }

       

        Arrays.sort(info, (o1, o2) -> {

            if(o1[1] == o2[1]){

                return o1[0] - o2[0]; // 두번째 같으면 첫번째 기준 오름차순

            }

            return o1[1] - o2[1]; // 두번째 기준 오름차순

        });

       

        int count = 0;

        int endTime = 0;

        for(int[] room : info){

            if(endTime <= room[0]){

                endTime = room[1];

                count++;

            }

        }

        System.out.println(count);

       

    }

}

 

 

---

잃어버린 괄호

 

 

import java.io.*;

import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer minus = new StringTokenizer(br.readLine(), "-");

        int sum = Integer.MAX_VALUE;

        while(minus.hasMoreTokens()){

            int temp = 0;

            StringTokenizer plus = new StringTokenizer(minus.nextToken(), "+");

            while (plus.hasMoreTokens()) {

                temp += Integer.parseInt(plus.nextToken());

            }

           

            if (sum == Integer.MAX_VALUE) { // 초기값 확인

                sum = temp;

            } else {

                sum -= temp;

            }

        }

        System.out.println(sum);

    }

}