[diamond5][해설,알고리즘 분류 안봄] 18185, 18186 라면사기

https://www.acmicpc.net/problem/18185

 

 

 

처음에 딱 봤을 때는 쉽게 풀릴 줄 알고 우선순위 큐 를 사용해 구현했지만...  실패 후 테스트 케이스를 보니 완전히 잘못 짰다는 걸 알았고.,..  아이디어를 떠올리기 위해 하루종일 고군분투했던 문제였다. 아이디어를 구현하는 건 그렇게 어렵지 않았지만 역시나  다이아의 품격이 느껴지는 그런 문제였다.

 

 

처음에 딱 보았을 땐  

이렇게 있으면 가장 왼쪽 포인트, 가장 오른쪽 포인트, 높이를 둔 객체를 우선순위큐에 넣어서 높이가 높은 순서대로 뽑아 바로 옆의 거랑 높이를 맞추면 된다고 생각했다. 위의 그림처럼 가장 높은 거부터 위를 쳐내고 옆의 거랑 높이가 같게 만든다면 될 거라고 생각했다. 빨간원 부분은 다른 부분과 연속되게 구매가 불가능 하다고 생각했기 때문이다. (즉 i , i + 1 2개만 가능하다고 생각했다)

그러나 크나큰 오해였다.

위 처럼 배열이 [1,2,1,1] 이렇게 있으면 앞의 연속된 2개를 구매하면 0,1,1,1  이 되어 3개를 연속으로 구매할 수 있게 된다....

즉 블럭으로(테트리스)로 생각해보면 빨간 원을 잘라내면 위에 있는 부분이 내려오는 것이다. 마치 테트리스와 같이 말이다.

여기서 완전히 잘못 생각했다는 것을 알았고, 처음부터 다시 생각했다.

이것저것 오랫동안 생각해본 결과 그럴듯 한 아이디어가 떠올랐다.

 

 

우선 1개를 살때 비용이 3, 2개를 연속해서 구매할 때 5, 3개를 연속해서 구매할 때 비용 7에서 숫자의 의미에 대해 생각해보자.

1개를 살때 3인데 2개를 구매하면 5이므로, 1 이득이다. 마찬가지로 2개를 살 땐 5이지만 3개를 살 땐 7이므로  2개 살때에 비해 1이득이다.

 

1개:3 -> 2개:5   :1개->2개 1이득

2개:5 -> 3개: 7  :  2개->3개 1이득

 

그렇다면 일단 무조건 3개를 연속으로 살려고 노력을 한다면, 손해를 볼일은 없을 것이다. 예를 들어 공장이 a,b,c,d 4개만 있다고 하면 a,b,c 에서 3개를 구매하다가 d에서 1개만 구매한다고 쳐도 7 + 3 = 10 이고,  a,b에서 2개, c,d에서 2개씩 살때도 5+5 =10이므로, 손해는 아니다.  

공장이 다섯개 있다고 하면 a,b,c에서 3개, d,e에서 2개이므로 무조건 이득이다.공장이  6개일때는  3개, 3개 이므로 말할 필요도 없다.

 

그렇다면 왼쪽에서 오른쪽으로 구매한다고 할 때 왼쪽부터 꽉꽉 채워서 3개씩 구매를 하도록 하면 되는 게 아닐까?

 

예를들면  a:1, b:2,c:3,d:4,e:5개를 사야된다고 할 때 a,b,c에서 3개, b,c,d에서 3개, c,d,e에서 3개 를 사고 나면

d는 2개, e는 4개가 남고, d,e에서 각각 2개씩 , e에서는 단품으로 2개.

 

이런식으로 진행될 것이다.

그러나 이것도 잘못된 생각이다. 예외가 있기 때문이다.

 

 

바로 왼쪽처럼 b가 고립되게 되어버리는 경우이다. 

왼쪽 : 3개연속 + 1개 + 1개

오른쪽 : 2개연속 + 3개연속

 

이므로 오른쪽이 2개연속 구매가 가능하므로 1이득이다.

무조건 연속 3개부터 채우자는 아이디어는 블럭이 순차적으로 증가할 때는 위에서 언급한 것처럼 타당하지만 아래처럼 고립되는 경우가 생길 땐 불가능 하다.

 

 

 

그럼 저런 경우에는 어떻게 대처할 까. 이부분에 대해 한참 고민했었다..

우선 케이스를 분류해 생각해보자.

 

case1.

 Hb > Ha && (Ha > (Hb - Hc))

 

 위와 같이 있을 때, 우리가 기존에 생각했던 대로 생각해보자 . 우선 계속 몇개 연속 구매라고 말하기 기니까 명칭을 정하면

 

1개 구매를 구매1,

2개연속 구매를 구매2,

3개연속 구매를 구매3

이라고 한다.

 

우선 우리가 먼저 생각한 방향대로 구매3을 최우선으로 하는 방향으로 간다면

구매3은 3번, 구매2는 2번, 구매1은 2번 가능할 것이다.

 

수식으로 말하자면

구매2: Ha -Hc 번

구매3 : Hc 번

 

 

그러나 우리는 이것이 최적의 결과가 아님을 직감하고 있다.

그러면 어떻게 해야 최적의 결과가 나올 수 있을 까.

소거법을 생각해보자. 우선적으로 구매1 부터 진행하는건 당연히 아니다. (구매1은 최후에 불가피할 경우에만 진행해야 함).

구매3부터 구매하는 것도 나중에  고립을 만들 수 있기 때문에 아니다.

그럼남은 건 구매2부터 진행하는 것이다. 문제는 구매2를 어디에서 몇번이나 진행해야 할 것인가?

b,c연속 구매는 우선 추천대상이 아니다. 왜그럴까?

우리는 아까 계단형 증가하는 방향일 때가 가장 이상적인 형태임을 알았다.

이런 형태 말이다. 이런 형태라면 고립없이 구매3을 왼쪽 부터 퍼펙트하게 채워나갈 수 있을 것이다.

 

그러나 b,c연속 구매는 상향 계단이 아닌 하향 계단을 만들어 버리고

ㄱㅗ립

고립을 만들게 된다.

그럼 남은건 a,b연속 구매이다.

문제는 구매2를 몇 번이나 해야 할 것인가

 

우선, Ha = Hc 가 될때 까지 자를 경우를 생각해본다.

구매2를 하는만큼, a, b도 낮아지므로 나중에 구매2를 해야하는 횟수가 줄어든다. 즉 쌤쌤이다. 지금 구매2를 하는만큼, 나중에 구매2를 덜해도 된다. 즉 손해는 없다.

Ha < Hc일 경우도 생각해본다.

여기서는 손해가 발생한다. 구매2를 하는만큼  a높이가 낮아져 구매3을 할 수 있는 횟수가 줄어든다.

하지만 이익도 있다. b의 높이가 낮아져 나중에 구매1을  해야하는 횟수가 줄어든다는 것이다. 즉 쌤쌤이다

그럼 언제까지 구매2를 반복해야 할까.

바로 Hb = Hc 일때까진데 만약 이때 추가로 더 구매2를 하게 된다면  b,c, d (나중에 나올)에서 충분히 구매3을 할 수 있는데 그 기회를 뺏는것이 된다. 즉 아래와 같이  Hb 가 낮아지면서 구매3의 기회가 줄어들게 된다. 만약 c가 마지막이고 d가 없다고 해도 지금 구매2를 하는만큼 구매2를 나중에 할 횟수가 줄어드는 것이므로 쌤쌤인 것이다.

즉 손해가 없을 수도, 손해가 발생할 수도 잇으므로, hb = hc일때까지만 구매2를 a,b에서 진행한다.

이를 수식으로 표현하면

구매1 : Hb - Ha

구매2 : Hb - Hc번

구매3 : Ha - (Hb - Hc) 번 이다.

 

 

아까 구매3을 우선적으로 진행했을 때는

구매2: Ha -Hc 번

구매3 : Hc 번

 이였다.

즉 구매2는  Hb - Ha 만큼 늘었고ㅡ 구매3는 Hb -Ha만큼 줄었다.

 구매3 우선시일 경우는 Hb - Ha만큼 구매3이 많고, 남은 구매1을 Hb-Ha만큼 진행해야한다.

구매2 우선시일 경우엔 Hb - Ha만큼 구매2이 많고, 남은 구매2를 Hb-Ha만큼 진행해야한다.

 

(Hb - Ha) * 구매3 + (Hb - Ha) * 구매1  = (Hb - Ha) * 구매2 + (Hb - Ha) * 구매2

이므로 구매2 우선시에도 손해가 없다. 단, 이경우는 a,b,c 만 있을 경우이다.

만약 뒤로 공장들이 쭉 있으면 (Hb-Ha) 만큼 (b,c,d)에서 구매3을 이어나갈 수 있으므로 무조건 이득이다.

즉 이득아니면 본전이다.

 

결론적으로 case1에서는 Hb = Hc가 될때까지 줄여야 한다.

 

 

case2.

 Hb > Ha && (Ha <= (Hb - Hc))

 

아까처럼 a,b에서 구매2를 진행하지만 Ha가 0이 되었을 때 b가 남으므로 필연적으로 구매1을 진행해야 한다.

구매1은 Hb = Hc가 될때까지 해야 할 것이다.

 

 

case3.

 Hb <= Ha  

이번 경우는 비교적 간단하다. 우선 Ha가  Hb 보다 크다면 필연적으로 고립되므로 Ha = Hb 가 될때까지 구매1을 진행한다.

그 후 만약 Hc > Hb 라면 우리가 바라는 우상향 계단형이므로, 스무스하게 진행하면 된다.

Hc < Hb라면  다시 a,b를 Ha=Hb = Hc 가 될 때까지 구매2를 반복해야 한다. (a, b도 필연적으로 고립되기 때문)

그후 구매3을 Hc번 진행

 

 

case4.우상향 계단

아까 언급한 대로 하면 된다.

 

이처럼 케이스를 나눠서 구하면 된다.

가장 생각하기 힘들었던 건 역시 case1이였다. 사실 논리적으로 저렇게 생각에 도달하는 건 매우 힘들 것이다. 계속 여러가지를 시도해보니 논리적으로 맞아 떨어졌던 것 뿐이다..

 

참 힘들고도 재미있는 문제였다. 이제 당분간은 이런 아이디어성 문제는 손대지 말아야 겠다..

 

 

 

 

 

번외:

 

우선순위 큐로 잘못짰던 코드. 그러나 다른 문제에 적용할 수 있을 것 같은 인사이트를 얻었으므로 (우선순위큐로 높이순으로 정렬하고,  같은 높이라면 위치 순서대로 정렬하게 하여 연속된 object에 대해 문제없이 꺼낼 수 있게 하는것) 뻘짓이 아니였다고 정신승리를 한다..

package boj18185;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Fail {
static int N;
static PriorityQueue<Integer[]> pq = new PriorityQueue<Integer[]>((a,b) -> {
if(b[1] == a[1]) return a[0] - b[0];
return b[1] - a[1];
}  );
static int ans = 0;
 static TreeSet<Integer[]> tree = new TreeSet<Integer[]>((a,b) -> a[0] - b[0]);

//static Integer[][] name = new Integer[10100][4];
static  int[] list = new int[10100];
static int[] root = new int[10100];
// a[0] : 이름, a[1] : 높이,a[2] :왼쪽 a[3] :오른쪽 

  public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i = 0; i < N ; i++) list[i] = Integer.parseInt(st.nextToken());
     
        int left = 0;
        
        for(int i = 0; i < N ; i++) {
         if(i == N - 1 || list[i] != list[i + 1]) {
         Integer[] union = new Integer[4];
         union[0] = left;
         union[1] = list[i];
         union[2] = left;
         union[3] = i;
         pq.add(union);
         tree.add(union);
         left = i + 1;
          
         }
        
        
        
        
        }
        
        for(int i = 0 ; i < N ; i++) {
        
         int leftPoint= pq.peek()[2];
         int height = pq.peek()[1];
         int rightPoint = 0;
        
         while(true) {
         Integer[] union = pq.poll();
         tree.remove(union);
         rightPoint = union[3];
         if(pq.isEmpty()) break;
         if(!(union[1] ==pq.peek()[1] && union[3] + 1 == pq.peek()[2] ))break;
         }
        
        Integer[] newUnion = new  Integer[4];
        newUnion[0] = leftPoint;
        newUnion[1] = height;
        newUnion[2] = leftPoint;
        newUnion[3] = rightPoint;
        
         //if(root[union[0]] !=  union[0])continue;
         Integer[] leftUnion = tree.lower(newUnion);
         Integer[] rightUnion = tree.higher(newUnion);
         
         int comp = 0;
         if(leftUnion == null && rightUnion == null) {
         comp = 0;
         }else if(leftUnion == null) {
         comp = rightUnion[1];
        
         }else if (rightUnion == null) {
         comp = leftUnion[1];
        
         }else {
         comp = rightUnion[1] > leftUnion[1] ? rightUnion[1] : leftUnion[1];
        
         }
        
         int width = newUnion[3] - newUnion[2] + 1;
         int cost = calculate(width);
         int totalCost = cost * (newUnion[1] - comp);
        
    //     System.out.println("width" + width + "cost" + cost + "totalCost" + totalCost);
         ans += totalCost;
        
         if(pq.isEmpty()) break;
        
         newUnion[1] = comp;
         pq.add(newUnion);
         tree.add(newUnion);
        
        }
        
        System.out.println(ans);
        
        
      
        
   
        
        
  }
  
  public static int calculate(int width) {
  int res = 0;
  res += 7 * (width / 3);
  if(width % 3 == 1) res += 3;
  else if(width % 3 == 2) res += 5;
  
  return res;
  
  
  
  }
}