[백준] 6359번 만취한 상범

March 14, 2021 ( last updated : March 14, 2021 )
dp 알고리즘 algorithm

Abstract

[백준] 6359번 만취한 상범

dp문제 중 하나입니다. 그냥 k배수 씩 돌면서 문을 열고 닫으면 됩니다.
따라서 dp[i*k]가 현재 문이 열려있는지 닫혀있는지를 확인하면 됩니다. 이는 0과 1로 확인이 가능함으로 간단히 다음과 같이 코드를 만들면 됩니다.

#include <cstring>
#include <iostream>

using namespace std;

int T, N;
int DP[101];

int main() {
  cin >> T;

  for (int i = 0; i < T; i++) {
    cin >> N;
    int cnt = 0;
    memset(DP, 0, sizeof(DP));
    for (int j = 1; j <= N; j++) {
      for (int k = 1; j * k <= N; k++) {
        if (DP[j * k] == 0) {
          DP[j * k] = 1;
        } else {
          DP[j * k] = 0;
        }
      }
    }
    for (int j = 1; j <= N; j++) {
      cnt += DP[j];
    }
    cout << cnt << endl;
  }

  return 0;
}

Originally published March 14, 2021
Latest update March 14, 2021

Related posts :

{# #}