[BOJ 백준] 15661번 1062번 (C++) | 백준 스터디 3주차

백준 스터디 3주차 (2022-03-29 TUE ~ 2022-04-04 MON 📚)

🥈 15661번 - 링크와 스타트

❔ 문제 바로가기

⭐ 풀이의 핵심

• 축구를 하기 위해 모인 사람은 총 N명이다. 이제 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다.
• 축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다.

• 어떤 팀이 스타트 팀이고, 어떤 팀이 링크 팀인지는 상관 없음
  한 팀의 인원을 뽑으면, 나머지 인원이 다른 팀이 되는 원리
  👉 next_permutation을 활용한 조합을 통해 1명, 2명, 3명, ... N/2명 뽑기
• N의 범위가 4<=N<=20으로 N*N 짜리 능력치 2차원 벡터를 반복문으로 두 번 정도 탐색하는 것은 문제 없음
  👉 팀 별로 능력치 2차원 벡터를 2중 for문을 돌며 탐색 및 능력치 계산 후 팀별 능력치 차이의 최솟값 업데이트

🔽 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <cmath>
using namespace std;

// 두 팀의 능력치 차이의 최솟값 minDiff
int minDiff = INT_MAX;
// skill[i][j]: Sij 값
vector<vector<int>> skill(20, vector<int>(20));

int getSkillSum(vector<int> team) {
    int teamSize = team.size();
    int skillSum = 0;
    for (int i=0; i<teamSize; i++) {
        for (int j=0; j<teamSize; j++) {
            if (i == j) { continue; }
            skillSum += skill[team[i]][team[j]];
        }
    }
    return skillSum;
}

int main() {
    int N;
    scanf("%d", &N);

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            scanf("%d", &skill[i][j]);
        }
    }

    // next_permutation을 활용한 조합 구하기
    // cf) 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다.
    // 1명 vs N-1명, 2명 vs N-2명, ... N이 짝수일 경우 N/2명 vs N/2명 또는 N이 홀수일 경우 N/2명 vs N/2+1명의 경우
    for (int i=1; i<=N/2; i++) { 
        vector<int> isSelected;
        for (int j=0; j<N-i; j++) { isSelected.push_back(0); }
        for (int j=0; j<i; j++) { isSelected.push_back(1); }

        do {
            // 임의로 두 팀에 각각 startTeam, linkTeam이라고 이름 붙이기
            vector<int> startTeam;
            vector<int> linkTeam;
            for (int j=0; j<N; j++) {
                if (isSelected[j]) { startTeam.push_back(j); }
                else { linkTeam.push_back(j); }
            }

            // 이번 경우의 두 팀의 능력치 차이 currDiff 
            int curDiff = abs(getSkillSum(startTeam)-getSkillSum(linkTeam));
            // minDiff 값 업데이트
            if (curDiff < minDiff) { minDiff = curDiff; }
        } while (next_permutation(isSelected.begin(), isSelected.end()));
    }

    printf("%d", minDiff);

    return 0;
}	

🥇 1062번 - 가르침

❔ 문제 바로가기

⭐ 풀이의 핵심

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

• prefix/postfix에 들어있는 a, n, t, i, c 최소 5개의 글자는 알아야 함
  • 단어를 입력받을 때 prefix "anta"와 postfix "tica"를 문자열에서 제외한 후 가르칠 글자 후보 탐색
  • 가르칠 글자 수 K가
    • 5보다 작다면 return 0;
    • 5보다 크거나 같다면 a, n, t, i, c 다섯 글자부터 가르칠 것
• 가르칠 글자 후보를 담는 unordered_set (아래 코드에서 candidatesSet) 활용
• 추가로 가르칠 글자 K-5개를 선택할 next_permutation 기반 조합 활용
• 글자의 가르침 여부를 체크할 unordered_map (teachingMap) 활용
  cf) 입력 조건 상 단어는 영어 소문자로만 이루어져 있음
  • map의 key는 알파벳 아스키코드 - 'a' 값 (즉 key 0번은 'a'를 의미)
  • map의 value는 0일 경우 가르치지 않음 1일 경우 가르침
• 가르칠 조합 경우의 수 별로 학생들이 읽을 수 있는 단어의 최댓값 업데이트 및 teachingMap 백트래킹

🔽 코드 (C++)

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;

// 학생들이 읽을 수 있는 단어 개수의 최댓값
int maxCount;

// cf) 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 
vector<char> defaultList = {'a', 'n', 't', 'i', 'c'}; 

// 가르칠 후보 알파벳들을 중복 없이 담기 위한 set
unordered_set<char> candidatesSet; 

// key: 알파벳 아스키코드 - 'a' 값 (즉 key 0번은 'a'를 의미), value: 0일 경우 가르치지 않음 1일 경우 가르침
unordered_map<int, int> teachingMap; 

void addCandidates(string str) {
    int len = str.size();
    for (int i=0; i<len; i++) {
        // a, n, t, i, c 중 하나라면 continue
        if (find(defaultList.begin(), defaultList.end(), str[i]) != defaultList.end()) {
            continue;
        }
        // 그 외 알파벳이라면 candidatesSet에 insert
        candidatesSet.insert(str[i]);
    }
}

bool isReadAble(string str) {
    int len = str.size();
    for (int i=0; i<len; i++) {
        // 한 알파벳이라도 가르치지 않은 경우 읽을 수 없음
        if (teachingMap[str[i]-'a'] == 0) {
            return false;
        }
    }
    // 읽을 수 있음
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;
    cin >> N >> K;

    vector<string> strList;
    for (int i=0; i<N; i++) {
        string str;
        cin >> str;

        // prefix 'anta' 삭제
        for (int i=0; i<4; i++) { str.erase(0,1); }
        // postfix 'tica' 삭제
        for (int i=0; i<4; i++) { str.pop_back(); }
        
        strList.push_back(str);
        addCandidates(str);
    }

    
    // a, n, t, i, c 최소 5개의 글자는 알아야 어떤 단어든 읽을 수 있음
    if (K < 5) {
        cout << 0;
        return 0;
    }
    K -= 5;
    for (int i=0; i<5; i++) {
        teachingMap[defaultList[i]-'a'] = 1;
    }

    // set을 vector로 변환
    vector<int> candidates;
    candidates.assign(candidatesSet.begin(), candidatesSet.end());
    int candidatesSize = candidates.size();

    // next_permutation을 활용한 조합으로 가르칠 알파벳 선택
    vector<int> isSelected;
    for (int i=0; i<candidatesSize-K; i++) { isSelected.push_back(0); }
    for (int i=0; i<K; i++) { isSelected.push_back(1); }
    do {
        // 선택된 알파벳 key에 대해 teachingMap value 변경
        for (int i=0; i<candidatesSize; i++) {
            if (isSelected[i]) {
                teachingMap[candidates[i]-'a'] = 1;
            }
        }

        // 이번 경우 학생들이 읽을 수 있는 단어의 개수 카운트
        int curCount = 0;
        for (int i=0; i<N; i++) {
            if (strList[i].empty() || isReadAble(strList[i])) {
                curCount++;
            }
        }

        // maxCount 값 업데이트
        if (curCount > maxCount) {
            maxCount = curCount;
        }

        // teachingMap 백트래킹
        for (int i=0; i<candidatesSize; i++) {
            if (isSelected[i]) {
                teachingMap[candidates[i] - 'a'] = 0;
            }
        }
    } while (next_permutation(isSelected.begin(), isSelected.end()));

    cout << maxCount;
    return 0;
}