백준 스터디 7주차 (2022-04-26 TUE ~ 2022-05-02 MON 📚)

🥈 16987번 - 계란으로 계란치기

❔ 문제 바로가기

⭐ 풀이의 핵심

재귀를 활용한 브루트포스 + 백트래킹 문제

계란의 수를 나타내는 N(1<=N<=8)
👉 작은 입력 조건

🚨 더 이상 깨지지 않은 계란이 없을 경우에 대한 예외 처리 필요

• bool eggsLeft; 변수로 체크
• eggsLeft == false 일 경우 가장 오른쪽 계란(마지막 계란)으로 바로 이동하여 계란을 치는 과정 종료

🔽 코드 (C++)

#include <iostream>
#include <vector>
using namespace std;

int N;
int maxBroken;
vector<pair<int, int>> eggs;

// eggs[i].first: durability, eggs[i].second: weight
void tryBreaking(int curr) {
    // 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.
    if (curr == N) {
        int broken = 0;

        // 깨진 계란(내구도가 0 이하인 계란) 개수 카운트
        for (int i=0; i<N; i++) {
            if (eggs[i].first <= 0) { broken++; }
        }

        // 깨진 계란의 최대 개수 업데이트
        if (broken > maxBroken) { maxBroken = broken; }
        return;
    }

    // 손에 든 계란이 깨졌으면 치지 않고 넘어간다. 
    if (eggs[curr].first <= 0 ) { 
        tryBreaking(curr+1);
        return;
    }

    // 깨지지 않은 계란 존재 여부 체크
    bool eggsLeft = false; 
    // 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 
    for (int i=0; i<N; i++) {
        if (eggs[i].first <= 0 || i == curr) { continue; }

        // 깨지지 않은 계란이 있는 경우 계란 치기 진행
        eggsLeft = true;
        eggs[i].first -= eggs[curr].second;
        eggs[curr].first -= eggs[i].second;
        tryBreaking(curr+1);
        // 백트래킹을 위해 복원
        eggs[i].first += eggs[curr].second;
        eggs[curr].first += eggs[i].second;
    }
    // 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다.
    if (!eggsLeft) { tryBreaking(N); }
}

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

    int durability, weight;
    for (int i=0; i<N; i++) {
        scanf("%d %d", &durability, &weight);
        eggs.push_back({durability, weight});
    }

    tryBreaking(0);

    printf("%d", maxBroken);

    return 0;
}

🥈 2784번 - 가로 세로 퍼즐

❔ 문제 바로가기

⭐ 풀이의 핵심

브루트포스 활용 구현 문제

6개의 줄에 알파벳 대문자로 이루어진 단어가 주어진다. 이 단어는 사전순으로 정렬되어 있다.

• next_permutation을 통해 순열(6!가지 경우) 구하기
• 구해진 순열의 앞에서부터 세 단어를 퍼즐의 가로에 놓기
• 구해진 순열의 뒤에서부터 세 단어가 퍼즐의 세로에 존재하는지 비교
  • 존재할 경우 퍼즐의 세로 단어에서 erase
    🚨 cf)
    세로에 있어야 하는 단어: BBB, CAA, CAA
    퍼즐의 세로에 존재하는 단어: BBB, CAA, BAA
    👉 erase하지 않을 경우 valid한 퍼즐이라고 인식할 수 있음
  • 존재하지 않을 경우 invalid한 퍼즐임을 표시한 후 break
• valid한 퍼즐인 경우 candidates 벡터에 push

만약 가능한 답이 여러개라면 사전순으로 앞서는 것을 출력한다.

• candidates 벡터를 sort한 후 candidates[0]에 해당하는 퍼즐 출력

🔽 코드 (C++)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

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

    vector<string> wordList(6);
    for (int i=0; i<6; i++) {
        cin >> wordList[i];
    }
    
    vector<string> candidates; // 퍼즐 후보를 담는 벡터
    do {
        string str = "";
        vector<string> vec; 

        // next_permutation으로 구한 순열의 앞에서부터 세 단어를 가로로 하는 퍼즐 구성
        for (int i=0; i<3; i++) {
            str += wordList[i];
            vec.push_back(wordList[i]);
        }
        
        vector<string> sero; // 현재 퍼즐의 세로를 구성하는 세 단어를 담는 벡터
        bool isValid = true;
        for (int i=0; i<3; i++) { // 퍼즐의 열
            string temp = "";
            for (int j=0; j<3; j++) { // 퍼즐의 행
                // 같은 열 다른 행의 문자들을 넣어 하나의 세로 단어 구하기
                temp += vec[j][i]; 
            }
            sero.push_back(temp);
        }

        // next_permuation으로 구한 순열의 뒤에서부터 세 단어와 퍼즐의 세로를 구성하는 세 단어 비교
        for (int i=3; i<6; i++) {
            auto iter = find(sero.begin(), sero.end(), wordList[i]);
            // 퍼즐의 세로 단어에 없을 경우 valid 하지 않은 퍼즐임을 표시하고 break
            if (iter == sero.end()) {
                isValid = false;
                break;
            }
            // 퍼즐의 세로 단어에 있을 경우 퍼즐의 세로 단어에서 매칭되는 해당 단어 erase
            else {
                sero.erase(iter);
            }
        }

        // valid한 퍼즐인 경우 candidates 벡터에 push
        if (isValid) {
            candidates.push_back(str);
        }
    } while (next_permutation(wordList.begin(), wordList.end()));

    // 6개 단어를 3*3 가로 세로 퍼즐에 놓을 수 없다면 0을 출력한다. 
    if (candidates.size() == 0) {
        cout << 0;
    }
    else {
        // 만약 가능한 답이 여러개라면 사전순으로 앞서는 것을 출력한다.     
        sort(candidates.begin(), candidates.end());

        for (int i=0; i<9; i++) {
            cout << candidates[0][i];
            if (i % 3 == 2) { cout << "\n"; }
        }
    }
    
    return 0;
}