[프로그래머스] 덧칠하기

덧칠하기

풀이

1. 그리디 알고리즘

그리디 알고리즘이란
전역 최적값을 찾기 위해 각 단계에서 로컬 최적 선택을 만드는 문제 해결 방법입니다. 즉, 미래의 결과나 결과를 고려하지 않고 현재 사용 가능한 최상의 옵션을 선택합니다.

예를 들어 47이라는 숫자가 있고 1, 5, 10, 25라는 숫자를 사용해 최적의 사용 숫자를 구하는 것입니다.

int[] coins = {1, 5, 10, 25};
int amount = 47;
int minNumCoins = minCoins(coins, amount);
System.out.println("Minimum number of coins needed: " + minNumCoins); 
// Output: Minimum number of coins needed: 4


public static int minCoins(int[] coins, int amount) {
    int numCoins = 0;
    Arrays.sort(coins);
    for (int i = coins.length - 1; i >= 0; i--) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            numCoins++;
        }
    }
    return numCoins;
}

이 문제에서는 배열 section의 값에서 부터 m값 만큼 더한 후 -1을 한 값을 검열하여 카운트 값을 구합니다.

답안

static int solution(int n, int m, int[] section) {
    int answer = 0;
    int max = 0;

    for(int i = 0; i < section.length; i++){
        int s = section[i];
        if(s > max) {
            answer++;
            max = s + m - 1;
        }
    }

    return answer;
}