[알고리즘] 특별한 물리 공격

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

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

class Main {
  static int N;
  static long[] R;
  static long[][][] dp;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    R = new long[N + 1];
    dp = new long[N + 1][2][2];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      R[i] = Long.parseLong(st.nextToken());
    }
    // 1: 학생 순서
    // 2: 현재 턴에서 0: 맞음, 1: 안맞음
    // 3: 이전 턴에서 0: 맞음, 1: 안맞음
    // 쉬이는 최소화하고 싶고 애들은 그걸 최대화하고 싶고
    dp[1][0][0] = R[1];
    dp[1][0][1] = 0;
    dp[1][1][0] = 0;
    for (int i = 2; i <= N; i++) {
      dp[i][0][0] = dp[i-1][0][1] + R[i];
      dp[i][0][1] = dp[i-1][1][0] + R[i];
      dp[i][1][0] = Math.max(dp[i-1][0][0], dp[i-1][0][1]);
    }
    System.out.println(Math.max(dp[N][0][1], dp[N][1][0]));
  }
}

나의 풀이

- 정말 고민을 많이 했던 문제

- 쉬이는 총 합이 최소가 되게 빔을 쏴야하고 반 애들은 그 최소를 최대가 되게 하고 싶고라는 조건이 정말 어려웠다.

- 뭔가 dp일 거 같다는 예감은 들었지만 어떻게 해야할지 감이 안왔으며 대머리를 어떻게 표현해야할지가 난관이었다.

- 대머리는 결국 안쏘는 것과 마찬가지라고 생각이 들었기 때문에 대머리를 안쏘는 것과 어떻게 구분해야하는지 어려웠던 것이다.

- dp 구성에 대해서 고민을 하다 결론이 나오지 않자 옛날에 풀었던 최소를 최대가 되게 하는 비슷한 형식의 문제로 보였던 프로그래머스의 징검다리 문제는 이분탐색이었기 때문에 이분탐색으로 풀고자 하였으나 유사한듯 보였으나 문제의 조건이 이분탐색을 사용할 수는 없게 되어 있었다.

- 그러다가 대머리는 어차피 없다고 치고 하는 거니까 구간을 세부적으로 나눠서 각 구간별로 dp를 구해서 합쳐가는 식으로 해결하면 되지 않을까 될거 같다는 느낌이 들었지만 논리적으로 생각을 해보니 풀 수가 없는 방법이었다.

- 결국 문제를 해결할 수 있게 된 아이디어는 '쉬이가 최소한으로 조건을 만족하도록 했을때 안 쏘는 부분은 대머리로 치환가능하다'는 것이다.

- 대머리로 치환해버리게 되면 어차피 쉬이는 그 하나의 방법 밖에 존재하지 않게 되기 때문에 자기 딴에는 그게 최소가 되어버리게 되는 것이다.

- 여기서 최소한의 조건이란 다음 두 가지 경우의 조합으로 쏘는 것이다. 

- 'XOOX'와 'XO'

- 즉, 이외의 부분은 예를 들어, OOO와 같은 패턴은 쉬이가 중간을 여전히 안쏠 수 있고 그러면 최소한의 방법이 안되기 때문에 안되는 것이다.

- 쉽게 말하면 저 패턴으로만 구성이 되었다는 것 = 쉬이가 최소한으로 쏨이다.

- 즉 저 패턴 중에서 최댓값이 쉬이가 최소한으로 쏘는 것 중 최댓값이 되는 것이다.

- 이를 구현하기 위해서는 현재 dp에 가지고 있는 값의 패턴이 어떤 것이었냐가 고려되어야 한다.

- 예를 들어, 현재 O인데 바로 이전 O에 대해 dp가 가지고 있는 패턴이 최신순으로 OO.. 였다면 안된다. OX..는 된다.

- 이런 걸 고려하기 위해 dp에는 몇번째 사람에 해당하는지, 그 사람은 O인지 X인지, 이전 사람은 O인지 X인지에 대한 정보를 저장해야 한다.

- 이를 고려해서 dp를 설계하면 아래와 같이 된다.

-  사람 지금 이전      사람 지금 이전

- dp[n][O][O] = dp[n-1][O][X]

- dp[n][O][X] = dp[n-1][X][O]

- dp[n][X][O] = max(dp[n-1][O][O], dp[n-1][O][X])

- 여기서 유의할 점은 첫번째 사람부터 해서 OOX..와 같다면 이건 또 안된다. 왜냐하면 쉬이가 첫번째를 X로 바꾸는게 최소가 되는 것이기 때문이다. 또한 마지막에서 XOO도 같은 이유로 안된다.

- 따라서 dp에서 첫번째와 마지막에 대해 예외 처리를 해주면 위의 코드가 된다.

 

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

class Main {
  static int N;
  static long[] R;
  static long[] dp;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    R = new long[N << 2 + 3];
    dp = new long[N << 2 + 3];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      R[i] = Long.parseLong(st.nextToken());
    }
    // 1: 학생 순서
    // 2: 현재 턴에서 0: 맞음, 1: 안맞음
    // 3: 이전 턴에서 0: 맞음, 1: 안맞음
    // 쉬이는 최소화하고 싶고 애들은 그걸 최대화하고 싶고
    dp[4] = R[1];
    dp[5] = 0;
    dp[6] = 0;
    for (int i = 2; i <= N; i++) {
      int doub = i << 2;
      int doub2 = (i - 1) << 2;
      dp[doub] = dp[doub2 + 1] + R[i];
      dp[doub + 1] = dp[doub2 + 2] + R[i];
      dp[doub + 2] = Math.max(dp[doub2], dp[doub2 + 1]);
    }
    System.out.println(Math.max(dp[(N << 2) + 1], dp[(N << 2) + 2]));
  }
}

비트마스크를 활용한 풀이

- 근데 오히려 메모리를 더 잡아먹고(2배 이상으로)(기존:36484 KB 현재:77100 KB) 시간도 느리다.

- 하나의 배열로 풀어보고자 시도했던 풀이

 

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

class Main {
  static int N;
  static long[] R;
  static long[]dp;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    R = new long[N + 1];
    dp = new long[N + 1];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      R[i] = Long.parseLong(st.nextToken());
    }

    // dp가 의미하는 건 i번째 학생이 맞는다는 전제하에 i번째 학생까지의 시이빔의 총합이 최소가 되게 하는 것의 최댓값
    if (N == 1) {
    	System.out.println(0);
	return;
    }

    dp[0] = 0;
    dp[1] = R[1];
    dp[2]= R[2];
    for (int i = 3; i <= N-1; i++) {
      dp[i] = Math.max(dp[i-2] + R[i], dp[i-3] + R[i-1] + R[i]);
    }
    System.out.println(Math.max(dp[N-2] + R[N], dp[N-1]));
  }
}

배열 하나 풀이

- 사고를 조금 바꾸어서 현재 dp에는 X값은 고려안하고 무조건 O에 대한 것만 저장한다고 하면 배열 하나로 풀이하는 것도 가능하다. 어떻게 O에 대한 dp를 만들때 X에 대한 dp는 필요가 없는 것일까? X는 규칙을 만들어내지만 그 자체가 더해지는 요소는 아니기 때문인듯하다. 

- 다시 정리를 해보면 애초에 dp는 O만 필요한 것이다. dp[X]는 필요가 없는 것이다. 왜냐하면 마지막에 답을 구할때 결국 O인 dp와 R 배열만으로 가능하기 때문이다. 이게 핵심이다. 답을 구하기 위해서 dp[X]는 필요가 없다. 결과론적 얘기 같아보이지만 dp 문제를 풀때에는 구해야 하는 답을 기준으로 배열이 어떤 요소를 담아야 하는지에 대해서도 고려가 필요하다는 것을 이를 통해 배울 수 있다. 근데 이 사고방식이 아직은 익숙하지 않아 훈련이 필요하

- dp[N] 전까지는 dp에는 O에 대한 것만 저장해 놓아도 된다. 이를 조합해서 그다음 dp값을 만들면 된다.

- dp 식을 만들때에는 두가지 경우 중 큰걸 선택하면 된다.(괄호가 현재) OXO[O], OX[O]

- 그리고 마지막에만 마지막이 X일때를 고려해서 답을 구하면 된다. 즉, 마지막 답을 구할때의 식 != dp를 구할때의 식인 것이다.

- 난 dp를 쓴다고 하면 dp식을 통해서 마지막 원소의 값도 구하고 이걸 답으로만 사용하는 것으로만 착각했는데 마지막에만 다른 식을 활용할 수 있다는 것을 배울 수 있었다.