[백준] 알고리즘 분류(브루트포스 알고리즘,JAVA)2851번, 슈퍼 마리오

문제 링크

2851번: 슈퍼 마리오

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 버섯은 순서대로 먹을 수 있으며 건너뛰지 못합니다.

2. 버섯 먹는 것을 멈추면 더이상 먹지 않습니다.

3. 마리오가 버섯을 먹을 때 100에 가장 가까운 수를 결과로 출력합니다.

4. 가장 가까운 수가 2개일 때 큰 값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 버섯을 먹는 누적합을 구한 뒤, 100에 가장 가까운 값을 탐색합니다.

 

3. 가장 가까운 값을 결과로 출력합니다.

 

 

버섯 먹은 점수

 

아래 버섯을 순서대로 먹을 때 

 

1

2

3

4

5

6

7

8

9

10

 

먹은 점수

1	2	3	4	5	6	7	8	9	10
1	3	6	10	15	21	28	36	45	55

 

100에 가장 가까운 점수 : 55점

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

1

2

3

5

8

13

21

34

55

89

 

2. 버섯을 먹는 누적합을 구한 뒤, 100에 가장 가까운 값을 탐색합니다.

 

순서대로 먹을 때 점수 누적합

 

1	2	3	5	8	13	21	34	55	89
1	3	6	11	19	32	53	87	142	231

 

100에 가장 가까운 점수 : 87

 

3. 가장 가까운 값을 결과로 출력합니다.

 

87를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 버섯의 점수를 이용하여 누적합을 구합니다.
• 누적합에서 100에 가장 가까운 값을 찾습니다.
• 가장 가까운 값을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

 

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] arr = new int[11];
        //버섯 점수 저장
        for(int i=1;i<=10;i++)
            arr[i] = arr[i-1] + Integer.parseInt(br.readLine());
        int dif = Integer.MAX_VALUE;	//숫자에서 100까지의 거리 최소값
        int answer = 0;
        for(int i=10;i>0;i--){
            int temp = Math.abs(100 - arr[i]);
            if(dif > temp){		//100까지의 거리가 더 작을 때
                dif = temp;		//100까지의 거리 최소값 변경
                answer = arr[i];	//현재값 가장 가까운 값으로 변경
            }
        }
        bw.write(answer + "");	//100에 가장 가까운 값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}