문제

문제 링크

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

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

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

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

입력

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

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

출력

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

제한

1 ≤ N ≤ 100,000

예제 입력

5
1 1 2 1 2

예제 출력

2

풀이

작년 말 원티드 쇼미더코드 2022 3회차에 지원해서 풀었던 문제이다. 그 땐 DP로 접근 해야지만 생각하고 어떻게 접근할 지 고민하다 풀지 못했던 문제이다.

처음엔 1차원 배열 DP로 어떻게 더하고 빼며 최대값을 구하려고 했지만, 왼쪽과 오른쪽 그 어느 방향의 최댓값도 구해지지 않았다. 조금 더 고민을 하다 생각난 방법이 최대 깨달음의 양을 왼쪽 오른쪽 두가지 기준으로 나눠서 진행하는 방법이었다.

오른쪽을 기준으로 삼았을 때 오른쪽이 나오면 이전 DP 값에 +1을, 왼쪽이 나오면 -1을 해준다. 만약 오른쪽 돌상이 나와 +1을 해줘야 하는데, 이전 DP값이 음수라면, 이전 값을 쓰는것보다 새로 시작하는게 무조건 값이 커진다. 그러므로 DP값을 1로 다시 시작했다.

왼쪽 기준으로도 똑같이 진행하여 두개의 DP 배열을 만든 후, 각 DP 배열의 최대값을 비교하여 출력했다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../ex.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const arr = input.shift().split(" ").map(Number);

// dp 두개 만들어서 체크하고 가장 큰 값 찾기
const dp1 = [arr[0] === 1 ? 1 : -1];
const dp2 = [arr[0] === 2 ? 1 : -1];

for (let i = 1; i < arr.length; i++) {
  const num = arr[i];
  if (num === 1) {
    if (dp1[i - 1] >= 0) {
      dp1[i] = dp1[i - 1] + 1;
    } else {
      dp1[i] = 1;
    }
  } else {
    dp1[i] = dp1[i - 1] - 1;
  }
}

for (let i = 1; i < arr.length; i++) {
  const num = arr[i];
  if (num === 2) {
    if (dp2[i - 1] >= 0) {
      dp2[i] = dp2[i - 1] + 1;
    } else {
      dp2[i] = 1;
    }
  } else {
    dp2[i] = dp2[i - 1] - 1;
  }
}

N === 1 ? console.log(1) : console.log(Math.max(...dp1, ...dp2));