[백준] 17968번 Fire on Field C++ 코드

코드

#include <iostream>

using namespace std;

int n, a[1003],check[1003];

int main() {
  cin >> n;
  a[0] = 1;
  a[1] = 1;
  for(int i = 2; i < n + 1; i++) {
    fill(check, check + 1003, 1);
    for(int j = 1; 2*j <= i; j++) {
      // 배열 인덱스 범위 확인
      if(2*(a[i - j]) - a[i - 2*j] > 1001 || 2*(a[i - j]) - a[i - 2*j] < 0) continue;
      check[2*(a[i - j]) - a[i - 2*j]] = 0; // 등차수열을 이루는 값은 거짓
    }
    // 1로 체크되어 있는 값 중 최소값을 저장
    for(int j = 1; j < n + 1; j++) {
      if(check[j]) {
        a[i] = j;
        break;
      }
    }
  }
  cout << a[n] << '\n';
  return 0;
}

등차수열을 이루면 안된다고 했으므로, 등차수열을 이루는 값들을 찾아 거짓이라고 체크한다. 그 후 check 배열을 돌면서 등차수열을 이루지 않는 최소값을 찾아주면 된다. 주의할 것은, 인덱스의 범위를 체크해줘야 한다는 것. 다른 문제 풀면서도 놓치지 말아야겠다.