백준 2786 자바 - 상근이의 레스토랑 (BOJ 2786 JAVA)

[ 백준 2786 - 상근이의 레스토랑 ]

[ 코드 보기 (깃헙 링크) ]

 

  

  쉬운 것 같으면서도 은근 생각할게 좀 있었다. 일단 생각 과정을 적어본다.

 

1. 첫 음식이 A가격이 아니고 B가격만 있었다면 어떻게 계산할까?

-> 음식을 입력받은 순서와 관계없이 B가격만 영향을 끼치므로, 그리디하게 B 가격 순서대로 구매한다고 생각하면 된다. 따라서 B를 기준으로 정렬한 후 prefix sum(누적 합) 배열 하나 만들어두면 쉽게 출력 가능하다. 결국 첫 음식은 A가격을 지불해야 하는 부분만 잘 처리하면 되는 문제이다.

 

2. 음식을 1개 시킬 때 최소 가격 : [전체 중 최소 A 값]

3. 음식을 n개(전부) 시킬 때 최소 가격 : [모든 B를 더한 값] + [(A-B)의 최소값]

-> 2,3번을 합쳐서 그럼 일단 A-B의 최소값과, A의 최소값이 의미가 있다는 것을 파악할 수 있음.

 

4. 누적합 구해둔 배열은 B값의 누적합 만 있다. 그럼 A값을 어떻게 계산에 추가할까?

4.1 i개의 음식을 샀을 때 산 음식 중 최소 A값이 있는 경우 : i개 음식을 산 경우의 누적합 + 구매한 음식 중 A-B의 최소값

 

e.g. 아래 배열은 입력된 순서와 관계없이, B값을 기준으로 정렬해둔 배열이다. 현재 4개의 음식을 먹으려 한다. 그럼 B값을 기준으로 앞의 4개를 고른다. 그리고 먹은 4개 중 A-B가 가장 작은 것을 첫 음식으로 먹으면 된다. 최소값은 16이 된다.

 

 

4.2 구매한 음식 이외에 최소 A값이 있는 경우 : i개의 음식을 살 것이지만, 구매한 음식 이외 중에 최소 A값이 있으므로 [누적합 중 i-1개의 음식을 더한값 + 최소 A값]

 

e.g. 현재 구하는 i가 4라고 할 때, 4까지의 prefix sum은 10이다. 이 중 하나를 첫번째에 넣어봐야 최소값은 16이 된다.

하지만 저 6번째에 있는 A가 1인 값을 첫번째 음식으로 선택해서 먹어버리면 1 + prefixSum[i-1] = 1+6 = 7이 된다.

 

5. 이 때 '4.2' 에서 주의할 점은 무조건 A가 작은게 외부에 있다고 해서 먹어버리면 안된다는 점이다. 결국 중요한건 최종적인 음식값이 최소가 되야 하는 것 이므로, 현재 상황에 맞춰서 4.1과 4.2 중 작은 값을 선택해야 한다. 그러려면 A값에 대해서도 [i 이상 중 최소 A값]에 해당하는 데이터가 필요하다. (사실 이게 제가 자꾸 틀린 이유였습니다 ㅠㅠ 처음엔 최소 A값 위치만 구해두고 해당 idx 이전은 전부 4.1로 처리하고, 최소 A값 idx이후를 확인할 땐 4.2로만 처리하면 될줄..)

 

 

6. 최종적으로 로직을 정리하면 다음과 같다.

 

a. 입력받은 음식의 A,B 값을 B값을 기준으로 정렬한다. (코드의 35 line)

 

b. 정렬된 배열을 기준으로 B값에 대한 prefix sum 배열과 a-b 배열, [i~N] 중 최소 A값 배열을 만든다. (코드의 38~48 line)

 

c. 4.1과 4.2 중 작은 값을 한줄씩 출력한다. (코드의 51~59 line)