백준 1433번: 화학 실험

N개의 용액을 섞어서 농도 M% 용액을 최대 몇 리터를 만들 수 있는지 구하는 문제이다.

 

M%와 같은 농도를 가진 용액은 이미 완성되어 있으므로 최종 리터에 추가한다. 나머지는 두 개의 리스트로 나누어 각각 낮은 농도, 높은 농도 용액을 넣었다.

static class Solution {
    
    int percent, liter, diff;
    
    Solution(int percent, int liter, int m) {
        this.percent = percent;
        this.liter = liter;
        this.diff = Math.abs(percent - m);
    }
}

double answer = 0.0;
List<Solution> lowerSolutions = new ArrayList<>(), higherSolutions = new ArrayList<>();
for (int i = 0; i < n; i++) {
    st = new StringTokenizer(br.readLine());
    int percent = Integer.parseInt(st.nextToken()), liter = Integer.parseInt(st.nextToken());
    if (percent == m) {
        answer += liter;
    } else if (percent > m) {
        higherSolutions.add(new Solution(percent, liter, m));
    } else {
        lowerSolutions.add(new Solution(percent, liter, m));
    }
}

 

 

최대한 많은 양의 농도 M% 용액을 만들기 위해, M%에 가까운 용액을 섞어야 한다. 이를 위해, 낮은 농도, 높은 농도 용액들의 각각의 최대 가용량을 구하여 최대한 섞을 수 있는 양을 구한 뒤, 농도차이가 적은 순서대로 각각의 리스트를 정렬한다.

double maxPosScore = 0;
for (Solution s : higherSolutions) {
    maxPosScore += s.liter * s.diff;
}

double maxNegScore = 0;
for (Solution s : lowerSolutions) {
    maxNegScore += s.liter * s.diff;
}
double targetScore = Math.min(maxPosScore, maxNegScore);

Collections.sort(lowerSolutions, Comparator.comparingInt(s -> s.diff));
Collections.sort(higherSolutions, Comparator.comparingInt(s -> s.diff));

 

 

이후, 정렬된 리스트 별로 최대한 섞을 수 있는 양에 섞으면서 만들 수 있는 최대 부피를 구한다.

private static double getVolumeToMatchScore(List<Solution> list, double targetScore) {
    double currentScore = 0;
    double volumeSum = 0;
    
    for (Solution s : list) {
        double remainingScore = targetScore - currentScore;
        if (remainingScore <= 0) {
            break;
        }
        
        double potentialScore = (double) s.liter * s.diff;
        if (potentialScore <= remainingScore) {
            volumeSum += s.liter;
            currentScore += potentialScore;
        } else {
            volumeSum += remainingScore / s.diff;
            currentScore = targetScore;
            break;
        }
    }
    return volumeSum;
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class 화학실험1433 {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
        double answer = 0.0;
        List<Solution> lowerSolutions = new ArrayList<>(), higherSolutions = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int percent = Integer.parseInt(st.nextToken()), liter = Integer.parseInt(st.nextToken());
            if (percent == m) {
                answer += liter;
            } else if (percent > m) {
                higherSolutions.add(new Solution(percent, liter, m));
            } else {
                lowerSolutions.add(new Solution(percent, liter, m));
            }
        }
        br.close();
        
        double maxPosScore = 0;
        for (Solution s : higherSolutions) {
            maxPosScore += s.liter * s.diff;
        }
        
        double maxNegScore = 0;
        for (Solution s : lowerSolutions) {
            maxNegScore += s.liter * s.diff;
        }
        double targetScore = Math.min(maxPosScore, maxNegScore);
        
        Collections.sort(lowerSolutions, Comparator.comparingInt(s -> s.diff));
        Collections.sort(higherSolutions, Comparator.comparingInt(s -> s.diff));
        answer += getVolumeToMatchScore(higherSolutions, targetScore);
        answer += getVolumeToMatchScore(lowerSolutions, targetScore);
        
        System.out.print(answer);
    }
    
    private static double getVolumeToMatchScore(List<Solution> list, double targetScore) {
        double currentScore = 0;
        double volumeSum = 0;
        
        for (Solution s : list) {
            double remainingScore = targetScore - currentScore;
            if (remainingScore <= 0) {
                break;
            }
            
            double potentialScore = (double) s.liter * s.diff;
            if (potentialScore <= remainingScore) {
                volumeSum += s.liter;
                currentScore += potentialScore;
            } else {
                volumeSum += remainingScore / s.diff;
                currentScore = targetScore;
                break;
            }
        }
        return volumeSum;
    }
    
    static class Solution {
        
        int percent, liter, diff;
        
        Solution(int percent, int liter, int m) {
            this.percent = percent;
            this.liter = liter;
            this.diff = Math.abs(percent - m);
        }
    }
}