[백준] 1062 가르침

April 27, 2021 ( last updated : April 27, 2021 )
비트마스크 알고리즘

https://github.com/sneakstarberry/

Abstract

[백준] 1062번 가르침

[백준] 1062번 가르침

백준 1062번

알고리즘 유형

문제 이해

남극 친구들이 읽을 수 있는 최대 단어수를 구하여라!

풀이방법

비트마스크를 응요하여 손쉽게 풀 수 있다.

#include <iostream>
#include <vector>
using namespace std;
int N, K, MAX_NUM = 0;
vector<string> WORDS;

void dfs(int letters, int count_ones, int alpha) {
  if (count_ones >= K) {
    int cnt = 0;
    for (int i = 0; i < WORDS.size(); i++) {
      int flag = 1;
      for (int j = 0; j < WORDS[i].size(); j++) {
        if ((letters & (1 << (WORDS[i][j] - 'a'))) == 0) {
          flag = 0;
          break;
        }
      }
      if (flag) {
        cnt++;
      }
    }
    if (cnt > MAX_NUM) {
      MAX_NUM = cnt;
    }
    return;
  }

  for (int i = alpha; i < 26; i++) {
    if ((letters & (1 << i)) == 0) {
      letters |= (1 << i);
      dfs(letters, count_ones + 1, i);
      letters &= ~(1 << i);
    }
  }
}

int main() {
  cin >> N >> K;

  if (K < 5) {
    cout << 0;
    return 0;
  }

  for (int i = 0; i < N; i++) {
    string tmp;
    cin >> tmp;
    WORDS.push_back(tmp);
  }

  int letters = 1 << ('a' - 'a') | 1 << ('n' - 'a') | 1 << ('c' - 'a') |
                1 << ('t' - 'a') | 1 << ('i' - 'a');
  dfs(letters, 5, 0);
  cout << MAX_NUM;
  return 0;
}

Originally published April 27, 2021
Latest update April 27, 2021

Related posts :

{# #}