[쇼미더코드 3회] 백준 27210 - 신을 모시는 사당 (자바 java)

 문제 : boj27210

---

 

필요 알고리즘 개념

• 구현, DP
  
  • 이전까지의 결과를 가지고 판단하는 DP 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  내 경우엔 좀 독특하게 푼 것 같다. 왼쪽과 오른쪽으로 기준을 나누어서 진행했다.

 

1. 왼쪽을 기준으로 생각하기

  왼쪽인 돌상을 +1, 오른쪽인 돌상을 -1이라고 해보자. 그럼 예제 입력 1은 다음과 같다.

'1 1 -1 1 -1'

 

그리고 왼쪽부터 차례대로 더하다가 음수가 나오는 부분은 버리면 된다.

예를들어 '1 1 -1 -1 -1 1 1 1' 이었다고 하면 순서대로 더해보면 1 -> 2 -> 1 -> 0 -> -1 -> 0 -> 1 -> 2이 된다. 이 때 음수가 나온 경우 음수인 구간을 애초에 무시해버리면 된다. 따라서 1 -> 2 -> 1 -> 0 -> -1(버림) -> 1 -> 2 -> 3 으로 마지막 3개를 구간으로 선택하는게 더 이득임을 알 수 있다. 

 

예제 입력 1의 경우엔 차례대로

1 -> 2 -> 1 -> 2 -> 1이 되므로 음수인 경우가 없었고, 이중 최대치는 2 이다.

 

2. 오른쪽을 기준으로 생각하기

  마찬가지로 이번엔 오른쪽인 돌상을 +1, 왼쪽을 -1로 둔다. 그럼 예제 입력 1은 다음과 같다.

'-1 -1 1 -1 1'

마찬가지로 왼쪽부터 차례대로 더해보면

-1(버림) -> -1(버림) -> 1 -> 0 -> 1 이 된다. 이 중 최대는 1이었다.

 

3. '1'과 '2' 중 더 높은쪽이 답임

  '1'일 때 최대치가 2였고, '2'일 때 최대치가 1이었으므로 2를 출력해주면 된다.

 

 

---

 

코드 : github

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

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        int max = 0;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int cur = arr[i] == 1 ? 1 : -1;
            sum += cur;
            if (sum > max) max = sum;
            if (sum < 0) sum = 0;
        }

        sum = 0;
        for (int i = 0; i < n; i++) {
            int cur = arr[i] == 1 ? -1 : 1;
            sum += cur;
            if (sum > max) max = sum;
            if (sum < 0) sum = 0;
        }

        System.out.println(max);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}