2851번(슈퍼 마리오)

첫 시도

• 버섯의 갯수가 10개로 고정, 완전탐색으로도 해결 가능
• 누적합을 사용 -> (100 - 누적합 값)의 절댓값을 구해 100과 얼마나 가까운지 계산
• 시간복잡도는 10 -> O(1)

해결

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int score = Integer.MAX_VALUE; // 100과 얼마나 가까이 있는지 알 수 있는 변수, score = Math.abs(100 - sum);
        int result = Integer.MIN_VALUE; // 가장 가까이 있는 수가 저장 될 변수
        int sum = 0;

        for(int i = 1; i < 11; i++){
            sum += Integer.parseInt(br.readLine());
            int temp = Math.abs(100 - sum); // 100에서 누적합의 값을 뺀 값의 절대값, 작을수록 100과 가까움
            if(score >= temp) { // >= 이므로 score가 같으면 같은 수 중 가장 큰 수가 저장됨
                score = temp;
                result = sum;
            }
        }
        System.out.println(result);
    }
}

참고

• 직접구현