Chapter11. 그리디 문제

Q01. 모험가 길드

문제

공포도가 x인 모험가는 반드시 x명 이상으로 구성한 모험가 그룹에 참여해야한다. 모험가 N명이 있을 때 여행을 떠날 수 있는 그룹 수의 최댓값을 구하여라.

풀이

처음에는 공포도가 높은 순서대로 묶었는데 [4,2,2,2,2]와 같은 경우를 생각해보니 되지 않아 다시 생각해봄. -> 공포도가 낮은 순서대로 그룹을 만들면 최대로 만들 수 있다.

한명씩 추가하면서 인원수가 공포도 이상이 되면 result(=모험가 그룹 수)를 1 증가시킨다.

코드

import java.util.*;

public class GreedyQ1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        List<Integer> people = new ArrayList<>();
        for (int i=0; i<N; i++){
            people.add(scanner.nextInt());
        }

        Collections.sort(people);

        int result = 0;
        int num = 0;

        for (int i=0; i<people.size(); i++){
            num += 1;
            if (num >= people.get(i)){
                result += 1;
                num = 0;
            }
        }
        System.out.println(result);
    }
}

 

Q02. 곱하기 혹은 더하기

문제

각 자리 숫자로만 이루어진 문자열이 주어졌을 때 x 또는 + 연산자를 넣어 가장 큰 수를 만들도록 해라.

풀이

한자리씩 연산을 하며 결과가 0인 경우는 더하고, 0이 아닌 경우는 연산할 값에 따라 다른 연산을 한다. -> 연산할 값이 0,1이면 +를 하고, 그 외의 값이면 *를 한다

코드

import java.util.Scanner;

public class GreedyQ2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] strings = scanner.nextLine().split("");

        int result = Integer.parseInt(strings[0]);
        for (int i=1; i<strings.length; i++){
            int n = Integer.parseInt(strings[i]);
            if (result == 0){
                result += n;
            } else {
                if(n==0){
                    result += 0;
                } else if(n==1){
                    result += 1;
                } else {
                    result *= n;
                }
            }
        }
        System.out.println(result);
    }
}