[Boj_15980] 명상 방해꾼

📎 문제 링크

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

 

▸ 문제

현욱은 신비로운 밀림 속에서 수행 중인 그의 스승님을 돕고 있다.

오늘은 스승님이 나무 밑에 앉아 명상을 하고 있고, 스승님 주변에는 새들이 앉아 있다. 새들이 지저귀면 스승님께 방해가 될 수 있기 때문에, 현욱은 그 중 한 마리를 잡아 지저귀지 못하게 하여 스승님의 명상을 도우려 한다.

새는 N마리가 있고, 각각 스승님의 왼편 또는 오른편에 앉아 있다. 스승님은 정신이 균형을 이루도록 집중하고 있는데, 정신의 중심은 왼편에 앉은 새가 지저귀면 음의 방향으로, 오른편에 앉은 새가 지저귀면 양의 방향으로 이동하게 된다. 각 새가 1초간 지저귀면 정신의 중심에 1만큼의 영향을 준다. 스승님은 총 M초간 명상하는데, 명상을 하는 중 정신의 중심의 절댓값이 최대가 된 순간, 그 절댓값이 스승님이 방해를 받은 정도가 된다.

현욱은 지금까지의 수련을 통해 새들의 지저귐을 예측할 수 있게 되었다. 현욱이 스승님이 방해를 가장 덜 받게 하기 위해 잡아야 할 새를 구해보자. 스승님의 정신의 중심은 처음에 0이고, 각 새가 스승님의 정신의 중심에 미치는 영향은 모두 독립적이며, 그 영향은 매 초가 끝날 때마다 동시에 적용된다.

 

▸ 입력

첫째 줄에 정수 N과 M이 공백을 사이에 두고 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 각 새에 대한 정보가 주어진다. 각 새에는 입력되는 순서대로 1부터 N까지의 정수 번호가 차례로 붙어 있다고 가정한다. 우선 L과 R중 하나의 문자가 주어지는데, L은 그 새가 스승님의 왼쪽에 있다는 뜻이고, R은 오른쪽에 있다는 뜻이다. 그 후 공백이 하나 주어진 뒤, 0과 1로 이루어진 길이 M의 문자열이 주어진다. 문자열의 i번째 문자는 i번째 초에 그 새가 지저귀는가에 대한 여부이고, 이 문자가 0이면 지저귀지 않는 것, 1이면 지저귀는 것이다.

 

▸ 출력

첫째 줄에는 현욱이 잡아야 할 새의 번호를 출력한다. 만일 잡을 수 있는 새가 여럿이라면 그 중 가장 작은 번호를 출력한다. 새는 반드시 한 마리 잡아야 한다.

둘째 줄에는 그 새를 잡았을 때 스승님이 방해받는 정도를 출력한다.

 

▸ 제한

1 ≤ N,M ≤ 2000

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 5
• 🔔  문제 유형 : 구현, 브루트포스 알고리즘, 누적 합
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

이 문제는 스승님이 명상 도중 가장 적게 방해받도록, 잡아야 할 새를 찾는 문제이다.

이때 누적 합(Prefix Sum)을 활용하여 해결할 수 있다.

 

각 새는 매 초 지저귀며, 스승님의 정신에 다음과 같은 영향을 준다.

• 왼쪽에 있는 새가 지저귀면 정신의 중심이 -1만큼 왼쪽으로 이동
• 오른쪽에 있는 새가 지저귀면 정신의 중심이 +1만큼 오른쪽으로 이동

여기서 주의할 점은, 스승님이 받은 방해의 정도는 명상 종료 시점의 값이 아닌, 매초 정신의 중심이 얼마나 흔들렸는지(절댓값) 중 가장 큰 값이라는 점이다.

 

먼저 각 초마다 모든 새가 지저귄 영향을 합산해 sum 배열을 만든다.

 

이 sum 배열을 이용해, 초마다 정신의 중심 위치를 누적 합으로 계산한다.

 

그런 다음, 각 새를 한 마리씩 제거하면서

그 새가 영향을 준 부분만 sum 배열에서 빼고, 다시 누적 합을 계산하여 흔들림의 최댓값을 구한다.

 

모든 새에 대해 이 작업을 반복하며, 스승님이 가장 적게 방해받는 경우를 찾는다.

만약 방해 정도가 동일한 경우가 여러 개라면, 번호가 가장 작은 새를 선택한다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 코드

메모리 : 59504KB
시간 : 564ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 새의 수
        int m = Integer.parseInt(st.nextToken()); // 명상 시간 (초)

        int[][] birds = new int[n+1][m]; // i번 새가 j초에 스승님의 정신에 준 영향
        int[] sum = new int[m]; // j초에 전체 새들이 정신에 준 영향의 총합
        String sounds;
        char dir;
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            dir = st.nextToken().charAt(0); // L 또는 R
            sounds = st.nextToken(); // 0 : 새가 안지저귐, 1 : 새가 지저귐

            for (int j = 0; j < m; j++) {
                if (sounds.charAt(j) == '1') { // 새가 지저귐
                    int value = dir == 'L' ? -1 : 1;
                    birds[i][j] = value;
                    sum[j] += value;
                }
            }
        }

        int num = 0; // 최소 방해를 준 새의 번호
        int level = Integer.MAX_VALUE; // 그 새를 잡았을 때 스승님이 방해받는 정도
        for (int i = 1; i <= n; i++) {
            int total = 0;
            int maxTotal = 0; // 절댓값 기준으로 정신이 가장 흔들린 순간의 크기

            for (int j = 0; j < m; j++) {
                total += sum[j] - birds[i][j]; // i번 새를 제거했을 때의 영향
                maxTotal = Math.max(maxTotal, Math.abs(total));
            }

            if (maxTotal < level) {
                num = i;
                level = maxTotal;
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(num).append("\n").append(level);

        System.out.println(sb.toString());

        br.close();
    }
}

 

진짜 오랜만에 푼 누적 합 문제였는데,, 해결 방법이 생각나지 않아 꽤나 오래 붙잡고 있었다.

요즘 문제도 안 읽히고 알테기가 온 것 같다.. 하지만 스트릭은 채워야지 😭