[백준] 12026 BOJ 거리 JavaScript

혅·2024년 11월 22일

JavaScript

백준, 프로그래머스 -JavaScript-

목록 보기

179/215

문제

BOJ 거리는 보도블록 N개가 일렬로 놓여진 형태의 도로이다. 도로의 보도블록은 1번부터 N번까지 번호가 매겨져 있다.

스타트의 집은 1번에 있고, 링크의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 점프해가려고 한다.

BOJ거리의 각 보도블록에는 B, O, J 중에 하나가 쓰여 있다. 1번은 반드시 B이다.

스타트는 점프를 통해서 다른 보도블록으로 이동할 수 있다. 이때, 항상 번호가 증가하는 방향으로 점프를 해야 한다. 만약, 스타트가 현재 있는 곳이 i번이라면, i+1번부터 N번까지로 점프를 할 수 있다. 한 번 k칸 만큼 점프를 하는데 필요한 에너지의 양은 k*k이다.

스타트는 BOJ를 외치면서 링크를 만나러 가려고 한다. 따라서, 스타트는 B, O, J, B, O, J, B, O, J, ... 순서로 보도블록을 밟으면서 점프를 할 것이다.

스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 1 ≤ N ≤ 1,000이 주어진다.

둘째 줄에는 보도블록에 쓰여 있는 글자가 1번부터 순서대로 주어진다.

출력

스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다.

예제 입력

9
BOJBOJBOJ

예제 출력

내가 했던 풀이

dp 배열을 N크기의 Infinity로 초기화해준다.
dp[0]을 0으로 초기화해준다. 처음 위치에서는 에너지가 0만큼 필요하기 때문이다.
1부터 N-1까지 i를 증가시키면서 반복한다. 현재 블럭의 글자에 따라 이전 블록이 다르므로 getPrev 함수를 통해 현재 글자 기준으로 이전에 밟을 수 있는 글자를 찾는다.
0부터 i-1까지 j를 증가시키면서 블럭이 prev(이전에 밟을 수 있는 글자)라면 해당 위치에서의 최소 에너지와 i까지 이동하는데 드는 에너지 (j-1)×(j-1)를 합한 에너지와 dp[i]의 값을 비교해서 더 작은 에너지를 dp[i]에 저장해준다.
모든 반복이 끝난 뒤 dp[N-1]에 저장된 값을 출력한다.

코드

const fs = require('fs');
let [N, block] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

block = block.trim().split('');

let dp = Array.from({ length: N }, () => Infinity);
dp[0] = 0;

function getPrev(current) {
  if (current === 'B') {
    return 'J';
  } else if (current === 'O') {
    return 'B';
  } else return 'O';
}

for (let i = 1; i < N; i++) {
  let prev = getPrev(block[i]);
  for (let j = 0; j < i; j++) {
    if (prev === block[j]) {
      dp[i] = Math.min(dp[j] + (j - i) ** 2, dp[i]);
    }
  }
}

console.log(dp[N - 1]===Infinity?-1:dp[N - 1]);