[Javascript/자바스크립트] 백준 17968번 Fire on Field

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

문제 해석

문제가 영어로 되어 있어서 정리를 좀 해봤다.

 

배열 A는 다음과 같은 규칙을 만족하는 수열이다.

• A[0]=1, A[1]=1이다.
• 어떤 k(k > 0)가 i - 2k ≥ 0이라는 조건을 만족시킬 때, A[i-2k], A[i-k], A[i]로 이루어진 부분수열은 등차수열이 되지 않는다. 즉, A[i]-A[i-k] ≠ A[i-k] - A[i-2k]이다.

예를 들어, A[2]는 1이 될 수 없다. 왜냐하면, A[0]=1, A[1]=1이기 때문에 A[2]가 1이면 A[0], A[1], A[2]는 공차가 0인 등차수열이 되기 때문이다. 그렇기에 A[2]는 A[0], A[1], A[2] 부분수열이 등차수열이 되지 않게 하면서도 가장 작은 양의 정수인 2가 되어야 한다.

 

입력으로 음수가 아닌 정수 n이 주어졌을 때, A[n]의 값을 구하는 프로그램을 만들자.

코드

let fs = require("fs");
let filePath = process.platform === "linux" ? "dev/stdin" : "./input.txt";
let n = +fs.readFileSync(filePath).toString().trim();

function solution(n) {
  let arr = [1, 1];
  for (let i = 2; i <= n; i++) {
    let possible = new Array(1000).fill(true);
    // 불가능한 수 찾아서 possible 배열에 표시
    for (let k = 1; k <= Math.floor(n / 2); k++) {
      if (i - 2 * k >= 0) {
        let impossible = 2 * arr[i - k] - arr[i - 2 * k];
        possible[impossible] = false;
      } else break;
    }

    // 가능한 수 중 가장 작은 양의 정수 찾기
    for (let j = 1; j < 1000; j++) {
      if (possible[j]) {
        arr.push(j);
        break;
      }
    }
  }
  return arr[n];
}

console.log(solution(n));

 

코드 설명

2부터 n까지 배열 A[i]의 값을 하나씩 구할 것이다.

1. A[i]의 값은 k가 1부터 시작하여 i - 2k < 0이 되기 전까지 탐색하며 불가능한 수들을 먼저 걸러낸다. 여기서 불가능한 수란, A[i] - A[i-k] == A[i-k] - A[i-2k]를 만족하는 수를 말하므로에 A[i-k]*2 - A[i-2k]를 불가능하다고 possible 배열에 표시해주면 된다.
2. 이제 걸러내고 남은 수 중 양의 정수이면서 가장 작은 수를 구한다. 그러니까 possible[j]가 true인 값을 구하면 된다.

이렇게 다 구한 뒤 arr[n]에 있는 값을 출력하면 된다.

 

느낀 점

영어 문제라서 좀 쫄았는데 천천히 읽어보니 별로 어렵지 않았다. 물론 문제 자체가 쉬운 문제라서 그런 것도 있지만...앞으로는 영어 문제를 만나게 되더라도 뒤로 가지 말고 읽어보고 해석해봐야겠다.