[백준] 1049번

사이트

https://www.acmicpc.net/problem/1049

1049번: 기타줄

 

 

문제 

 

분석

초반에 문제가 이해가 안되었지만 집중해서 읽으니 나름 쉬운 문제 였다. 

 

일단 요점을 파악해야된다. 

적어도 N개를 사기 위해!! 적어도!! 이 적어도라는 말이 중요하다. 

필자는 N개를 딱 맞춰서 그에 맞는 최소 비용인줄 알았으나 아니었다. 

즉 N개 이상이 되도 최소비용이면 된다는 것이다!! 

 

그럼 필자는 어떻게 해결했을까? 

sett = new int[m + m];
one = new int[m];

다음과 같이 배열을 만들었다.

sett는 6개 세트 배열이고 one 배열은 낱개이다.

근데 sett 만 크기를 곱하기 2배한 이유는 낱개를 6을 곱해서 똑같이 넣어주기 위함이다.

for (int i = 0; i < one.length; i++) {
    copy_one[i] = one[i];
    one[i] *= 6;
    sett[i + m] = one[i];
}

즉 이렇게 낱개도 6개를 곱해서 넣어주면 세트로 한방에 사는것이 더 최소일때도 있기 때문이다. (뒤에서 설명)

 

이젠 본론으로 들어가서 

Arrays.sort(copy_one);
Arrays.sort(sett);

낱개배열을 카피한 copy_one 배열과 sett(낱개* 6 포함) 배열을 오름차순으로 정렬했다. 

 

if (n < 7) {
    return Math.min(sett[0], copy_one[0] * n);
}

그 후 기타줄이 6개 이하면 if 문을 써서 6개 이하인것만 따로 로직을 만들었다. 

 

이것은 세트별로 사는게 낫나 아니면 낱개*기타줄(6개 이하만) 로만 사는게 낫나!! 

즉 6개 이하기 때문에 애초에 세트 vs 낱개*기타줄 구도로 된다!! 

 

int mok = n / 6;
int reminder = n % 6;

int result1 = sett[0] * (mok + 1);
int result2 = sett[0] * mok + copy_one[0] * reminder;

return Math.min(result1, result2);

 

다음은 7개 이상일때다! 

여기서 핵심은 기타줄이 10개일때 6으로 나누어 세트(6) 즉 몫과, 낱개 즉 나머지를 구하는것이다.

그럼 1 하고 4가 나올것이다. 

 

sett[0]은 애초에 세트하고 낱개*6해서 나온 결과들 중 젤 최솟값이 나온 값이다. 

즉 sett[0] 값이랑 mok+1해서 원래 고쳐야될 기타 줄 개수보다 개수의 최소 비용이랑(ex 지금 기타줄이 10개면 12개가 됨)

 

아님 기타줄 갯수랑 딱 맞춰서(세트 + 낱개) 계산할때 Math.min 함수를 써서 계산하면 끝이다!! 

 

여기서 후자 방법이 의문인게 만약 고쳐야될 기타수가 16이고 세트2 낱개4가 나올경우 

세트1 낱개10 으로 계산할 수 있지 않나? 라고 생각할 수 있는데 이것은 명백한 실수다.

왜냐하면 sett[] 배열에서 낱개*6도 포함시켰기 때문에 다 계산해서 나온 최솟값이기 때문에 

세트2 낱개4로 하는 것이 바람직하다.

세트1 낱개10 이렇게 하면 낱개가 최소일때만 가능하지 오리지널 세트가 최소일때는 나오지 않는다.

 

 

전체 코드

package greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Greedy1049 {
    static int n;
    static int[] sett;
    static int[] one;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        sett = new int[m + m];
        one = new int[m];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            sett[i] = Integer.parseInt(st.nextToken());
            one[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(solution(m));
    }

    public static int solution(int m) {
        int[] copy_one = new int[m];
        for (int i = 0; i < one.length; i++) {
            copy_one[i] = one[i];
            one[i] *= 6;
            sett[i + m] = one[i];
        }
        Arrays.sort(copy_one);
        Arrays.sort(sett);

        if (n < 7) {
            return Math.min(sett[0], copy_one[0] * n);
        }

        int mok = n / 6;
        int reminder = n % 6;

        int result1 = sett[0] * (mok + 1);
        int result2 = sett[0] * mok + copy_one[0] * reminder;

        return Math.min(result1, result2);
    }
}

 

결과

느낀점

if문에서 따로 수학함수를 놓지 않아서 틀렸다... 

그치만 바로 인지하고 고쳤다. 

그다지 어렵진 않았지만 역시 그리디라 그런지 살짝 두려웠다...