[백준 27210] 신을 모시는 사당(JAVA)

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

285

124

98

47.573%

문제

신을 모시는 사당에는 신을 조각한 돌상 N개가 일렬로 놓여 있다. 각 돌상은 왼쪽 또는 오른쪽을 바라보고 서있다. 창영이는 연속한 몇 개의 돌상에 금칠을 하여 궁극의 깨달음을 얻고자 한다.

궁극의 깨달음을 얻기 위해서는 가능한 한 많은 금색 돌상들이 같은 방향을 바라보아야 한다. 방향이 다른 돌상은 깨달음에 치명적이다. 깨달음의 양은 아래와 같이 정의된다.

| (왼쪽을 바라보는 금색 돌상의 개수) - (오른쪽을 바라보는 금색 돌상의 개수) |

창영이는 궁극의 깨달음을 얻을 수 있을까?

입력

첫째 줄에 돌상의 개수 N이 주어진다.

둘째 줄에 돌상이 나열된 순서대로, 각 돌상이 바라보고 있는 방향이 주어진다. 입력의 편의상 왼쪽은 1, 오른쪽은 2라고 하자.

출력

최대한 많은 깨달음을 얻기 위해 금을 칠하였을 때, 얻을 수 있는 깨달음의 양을 출력한다.

제한

• 1 ≤ N ≤ 100,000

---

https://usedto-wonderwhy.tistory.com/entry/%EB%B0%B1%EC%A4%80-1912-%EC%97%B0%EC%86%8D%ED%95%A9-DP

[백준 1912] 연속합 (DP)

위 문제와 거의 유사하다.

왼쪽을 바라보는 금색 돌상의 개수를 -1 이라고 정의하고 오른쪽을 바라보는 금색 돌상의 개수를 +1 이라고 정의하면

주어진 입력은 -1, +1 로 이루어진 하나의 연속 수열이 되며,

 

해당 수열에서 구할 수 있는 연속합의 최대를 구하면 된다.

 

dp [ i ] 를 i 번째까지의 최대 연속합이라고 정의하면,

dp [ i ] = Max ( dp[i-1]+arr[i] , arr[i] ) 와 같다.

(i-1 번째까지의 최대 연속합에 현재 i 번째 원소를 더한 것과, 현재 i 번째 원소 중 더 큰 값이 i 번째까지의 최대 연속합)

 

다만, 왼쪽을 -1, 오른쪽을 +1 로 바라본 경우와

왼쪽을 +1, 오른쪽을 -1 로 바라본 경우를 각각 구하여 둘 중 최대값을 구해주는 것을 유의해야 한다.

 

이를 구현하면 아래와 같다.

 

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 {
        int n;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stk.nextToken());
        int[] arr = new int[n];

        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(stk.nextToken());
        }

        int[] dp = new int[n];
        int ans = -10;
        for (int i = 0; i < n; i++) {
            int cur = arr[i] == 1 ? -1 : 1;
            if (i == 0) {
                dp[i] = cur;
            } else { // i!=0
                dp[i] = Math.max(dp[i - 1] + cur, cur);
            }
        }
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, dp[i]);
        }

        dp = new int[n];
        for (int i = 0; i < n; i++) {
            int cur = arr[i] == 1 ? 1 : -1;
            if (i == 0) {
                dp[i] = cur;
            } else { // i!=0
                dp[i] = Math.max(dp[i - 1] + cur, cur);
            }
        }
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
    }
}