코딩 테스트

[백준] 20115번 에너지 드링크(그리디) - 실버3

한 면만 쓴 종이 2023. 1. 15. 20:25

 

페인씨가.. 많이 피곤했나보군..

 

에너지 드링크들을 합치는 과정

1. 임의의 서로 더른 두 에너지 드링크를 고른다.

2. 한쪽 에너지 드링크를 다른 쪽 에너지 드링크에 모두 붓는다. >>단, 페인은 야근 후유증으로 인해 손이 떨려, 붓는 과정에서 원래 양의 절반을 바닥에 흘리게 된다<<

3. 다 붓고 남은 빈 에너지 드링크는 버린다.

4. 1~3 과정을 에너지 드링크가 하나만 남았을 때까지 반복한다.

 

페인씨는 절반을 흘려도 최대 양의 에너지 드링크를 드시려고 하는 군.. 하하

 

 

흠 이 문제는 그리디 문제라고 하니까 그리디를 공부해보자! 학교 수업때 배운거 같지만 ,, 내 머리는 ,,, 기억하지 못해 오 탐욕 알고리즘이라고 하니까 생각난다. 자구시간에 배운듯

 

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬 (hanamon.kr)

 

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬

❗️탐욕 알고리즘(Greedy Algorithm)이란? Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다. 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에

hanamon.kr

매우 잘 설명해주셨군요.. 감사합니당

 

 

음 근데 문제 고를 때는 그리디라고 해서 골랐는데 걍 제일 양 많은거에 다 반씩만 해서 담으면 될 것 같은뎅..

일단 코드를 짜보겠슴둥

 

아! 그리고 이번에는 BufferedReader를 사용해볼게용~ 속도가 매우 빨라진다고 합니당

 

버퍼를 사용하면 키보드의 입력이 있을 때 마다 한 문자씩 버퍼로 전송해서 버퍼가 가득 차거나 개행 문자가 나타나면 버퍼의 내용을 한 번에 프로그램에 전달한다고 한다!

 

 


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        String s = br.readLine();
        String[] tmp = s.split(" ");
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (String n : tmp) list.add(Integer.parseInt(n));

        System.out.println(amount(list));

    }

    static double amount(ArrayList<Integer> list) {

        int max = Collections.max(list);
        list.remove(max);
        double total = max;
        for (int n : list) {
            System.out.println(n);
            total += (double)n / 2;
        }
        return total;

    }
}

 

첫 시도! 역시나 실패!

ArrayIndexOutOfBoundsException 오류 발생 ㅠ

 

크크 remove를 잘못했다

list.remove(Integer.valueOf(max));

이렇게 고쳤더니 잘 돌아가는 군

 

이제 제출해보겠슴둥

 

와우 한 번에 성공!! 정말 간만이군용

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        String s = br.readLine();
        String[] tmp = s.split(" ");
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (String n : tmp) list.add(Integer.parseInt(n));

        System.out.println(amount(list));
    }

    static double amount(ArrayList<Integer> list) {
        int max = Collections.max(list);
        list.remove(Integer.valueOf(max));
        double total = max;
        for (int n : list) total += (double)n / 2;
        
        return total;
    }
}

☝️ 최종 제출본!