#탐욕알고리즘 #짐나르기 #편의점알바 #자리 옮기기# 금고털기

최적의 상황을 찾는것 자체가 정렬을 한 후 인덱스 번호끼리 비교하는 것이라고 생각

짐나르기
1. 항상 나갈 수 있는 최적을 찾아야한다 — 무게를 오름차순 정렬을 한다

만약 작은거 두개끼리 나가면 의미가 없고 너무 많은 많은 상황이 생긴다

큰것만 하나씩 나간다면 한 번에 나갈 수 있는 최적이 아니다

그렇기 때문에 가장 큰 것 + 가장 작은 것이 제한을 넘지 않아서 한 번에 나가는게 가장 최적이다

가장 작은 것과 가장 큰것을 더 했을때 제한이 넘으면 가장 큰것만 혼자 나간다

가장 작은 것과 그 다음 큰것을 더해서 제한과 비교한다 그후 제한 보다 작으면 두개를 같이 내보낸다

그리고 다음 작은것과 다음 큰것을 비교해서 반복한다

    Arrays.sort(stuff);

    int min = 0;
    int max = stuff.length-1;
    int count =0;
    while(min <= max){
      if(stuff[min] + stuff[max] <= limit){
        min++;
        max--;
        count++;
      }else{
        max--;
        count++;
      }
    }
    return count;
  } 
}

편의점 알바

코인 {500, 100, 50, 10, 5, 1}
1. 가장 큰 동전을 몇개까지 줄 수 있는지
2. 가장 큰 동전을 주고 나머지를 구함
3. 나머지에서 그 다음 큰 동전을 몇개 줄 수 있는지
4. 해당 동전의 금액만큼 빼고 다음 동전을 생각
5. 반복

  public int partTimeJob(int k) {
    // TODO:
    int[] coin = new int[]{500,100,50,10,5,1};
    int hap=0;
    int result =0;
    for(int i=0;i<coin.length;i++){
      if(k>=0){
        hap = k/coin[i];
        result += hap;
        k -= hap*coin[i];
      }
    }
    return result;
  } 
}
//k>=500
//k/500 * 동전
//k%500/100
//k%500%100/50
//k%500%100%50/10
//k%500%100%50%10/5
//k%500%100%05%10%5

보드게임

    // TODO:
    int sum=0;
    int a =0;
    int b =0;
    char[] move = operation.toCharArray();
    for(int i=0;i<move.length;i++){
      if(move[i]=='U'){
        a = a -1;
      }else if(move[i]=='D'){
        a = a +1;
      }else if(move[i]=='L'){
        b = b -1;
      }else if(move[i]=='R'){
        b = b +1;
      }
      if(a<0 || b<0){return null;}
      if(a>board.length || b>board.length){return null;}

      sum += board[a][b];
    }
    return sum;
  } 
}
// [0,0,1]
// [1,0,1]
// [1,1,1]