[백준] 알고리즘 분류(그리디 알고리즘,JAVA)2828번, 사과 담기 게임

문제 링크

2828번: 사과 담기 게임

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 한 사과가 바닥에 닿을 때 다음 사과가 떨어지기 시작합니다.

2. 바구니는 왼쪽 M칸을 차지하고 있습니다.

3. 바구니는 오른쪽, 왼쪽으로 이동이 가능합니다.

4. 사과를 바구니에 모두 담을 때 이동하는 최소 거리를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 모든 사과를 바구니에 담는 과정을 탐색합니다.

 

3. 모든 과일을 담은 후 이동한 거리를 결과로 출력합니다.

 

 

바구니에 사과 담기!

 

 

바구니의 넓이 : M

 

바구니의 시작 위치 : start

 

바구니의 끝 위치 : end

 

따로 저장한 뒤 바구니를 이동합니다.

 

 

바구니의 끝 위치 < 사과의 위치

 

오른쪽으로 이동!

 

start = start + (사과의 위치 - end)

 

end  = 사과의 위치

 

 

바구니의 시작 위치 > 사괴의 위치

 

왼쪽으로 이동!

 

end = end - (start - 사과의 위치)

 

start = 사과의 위치

 

 

예제입력 2.

 

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

 

N = 5

M = 2

J = 3

 

사과 떨어지는 위치 정보

	사과 1	사과 2	사과 3
위치	1	5	3

 

2. 모든 사과를 바구니에 담는 과정을 탐색합니다.

 

바구니의 사과 담기!

 

사과 1
Start (	) End

 

Start = 1

End = 2

 

사과 1이 그대로 떨어져도 바구니에 담을 수 있기 때문에 이동하지 않습니다.

 

 

				사과 2
Start (	) End

사과의 위치 : 5

End(2) < 사과의 위치(5) 성립!

오른쪽 이동!

Start = Start + (사과의 위치 - End) = 1 + (5 - 2) = 4

End = 사과의 위치 = 5

 

				사과 2
			Start (	) End

바구니를 오른쪽 3칸 이동한 뒤 사과 2를 바구니에 담았습니다.

 

		사과 3
			Start (	) End

사과의 위치 : 3

Start(4) < 사과의 위치(3) 성립!

왼쪽 이동!

End = End - (Start - 사과의 위치) = 5 - (4 - 3) =  4

Start = 사과의 위치 = 3

 

		사과 3
		Start (	) End

바구니를 왼쪽 1칸 이동한 뒤 사과 2를 바구니에 담았습니다.

 

3. 모든 과일을 담은 후 이동한 거리를 결과로 출력합니다.

 

사과 2를 먹을 때 오른쪽 3칸 이동

 

사과 3을 먹을 때 왼쪽 1칸 이동

 

이동한 칸 4를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 N과 M을 띄어쓰기 기준 나누었습니다.
• 각 사과를 순서대로 바구니를 이동하며 담습니다.
• 모든 사과를 담았을 때 바구니의 이동 거리를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.*;

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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int j = Integer.parseInt(br.readLine());
        int answer = 0;	//이동 횟수 저장 변수
        int start = 1, end = M;	//바구니 시작, 끝의 위치
        //사과 바구니에 담기 탐색!
        for(int i=0;i<j;i++){
            int apple = Integer.parseInt(br.readLine());
            if(start > apple){		//시작 위치 > 사과 위치
                answer += start - apple;	//이동한 거리 더하기
                end -= start - apple;	//끝 위치 변경
                start = apple;		//시작 위치 변경
            }else if(end < apple){	//끝 위치 < 사과 위치
                answer += apple - end;	//이동한 거리 더하기
                start += apple - end;	//시작 위치 변경
                end = apple;	//끝 위치 변경
            }
        }
        bw.write(answer + "");		//이동 거리 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}