[백준 2828번: 사과 담기 게임] java풀이

🔔Thinking

그리디 알고리즘(탐욕 알고리즘)

선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

• 그리디 알고리즘의 해결 과정

1. 선택 절차: 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사: 최적해가 아니면 이전 절차로 돌아가 위의 과정을 반복한다.

• 그리디 알고리즘의 성립 조건

1. 탐욕적 선택 속성: 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

문제 해결 과정

1. 스크린과 바구니를 배열로 구현함. 바구니는 스크린 위에서 좌우로 움직임
2. 바구니의 처음 위치는 스크린 배열의 첫번째 인덱스부터 시작함
   -> left=0, right = left+m-1(m은 바구니 넓이)
3. 스크린 위로 사과가 떨어질때마다 바구니를 옮기면서 무조건 담는다
   -> 바구니보다 사과가 왼쪽에 있으면 거리차이 = left - apple
   -> 따라서 바구니는 왼쪽으로 가므로 left, right를 거리차이만큼 감소
   -> 바구니보다 사과가 오른쪽으로 떨어지면 거리차이 = apple - right
   -> 따라서 바구니는 오른쪽으로 가므로 left, right를 거리차이만큼 증가

🔑Solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       int m = sc.nextInt();
       int screen[]=new int[n];//스크린
       int basket[]=new int[m];//바구니
       int left=0,right=left+m-1;//바구니 위치 인덱스 표현

       int j = sc.nextInt();
       int distance=0; //거리
       for(int i=0; i<j; i++){
           int apple=sc.nextInt()-1;//사과 위치
           if(apple<left){
               int diff=left-apple; //사과와 바구니 거리차이
               distance+=diff;
               //바구니 왼쪽으로 이동
               left-=diff;
               right-=diff;
           }
           else if(apple>right){
               int diff=apple-right; //사과와 바구니 거리차이
               distance+=diff;
               //바구니 오른쪽으로 이동
               right+=diff;
               left+=diff;
           }
       }
       System.out.println(distance);
    }
}