[백준 BOJ] 2531번 13908번 (C++) | 백준 스터디 5주차

백준 스터디 5주차 (2022-04-12 TUE ~ 2022-04-18 MON 📚)

🥈 2531번 - 회전초밥

❔ 문제 바로가기

⭐ 풀이의 핵심

슬라이딩 윈도우 활용
특정 조건을 만족하는 고정적인 길이의 연속 구간에 대해 살펴보고자 할 때 활용하는 알고리즘
가변적인 구간을 살펴보는 투포인터 방식과 달리 포인터가 하나만 있어도 OK
ex) 1 2 3 4 5 에 크기 3짜리의 슬라이딩 윈도우 적용 시
👉 [1 2 3] 4 5 -> 1 [2 3 4] 5 -> 1 2 [3 4 5]

🔽 코드 (C++)

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

int main() {
    int N, d, k, c; // 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c
    scanf("%d %d %d %d", &N, &d, &k, &c);

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

    // 슬라이딩 윈도우 활용
    int maxCount = 0;
    for (int i=0; i<N; i++) {
        vector<bool> sushiAte(d); // sushiAte[i]: true일 경우 i번 초밥을 이미 먹음, false일 경우 먹지 않음
        int alreadyAte = 0; // 윈도우 내에서 중복되는 번호의 초밥 개수
        int couponLeft = 1; // 1일 경우 쿠폰으로 다른 초밥을 먹어볼 수 있음, 0일 경우 이미 먹음

        for (int j=i; j<i+k; j++) { // 연속 k개 확인
            // 이미 먹어본 초밥일 경우
            if (sushiAte[dishes[j%N]]) { alreadyAte++; } 

            // 먹어보지 않은 초밥일 경우
            else { sushiAte[dishes[j%N]] = 1; }
        }
        // 쿠폰 번호의 초밥을 이미 먹어본 경우
        if (sushiAte[c]) { couponLeft = 0; }

        int count = k - alreadyAte + couponLeft; // 이번 윈도우에서 먹을 수 있는 초밥의 가짓수
        
        // 최대 가짓수 업데이트
        if (count > maxCount) { maxCount = count; }
    }
    
    printf("%d", maxCount); 
    
    return 0;
}

🥈 13908번 - 비밀번호

❔ 문제 바로가기

⭐ 풀이의 핵심

입력 조건을 보면 비밀번호의 길이 n의 범위는 1 이상 7 이하로
비밀번호의 길이가 가장 길고 선견지명으로 알게된 비밀번호에 들어가는 수가 0개여도
가능한 모든 경우의 수가 7!으로 크지 않기 때문에
브루트포스로 해결 가능

DFS+백트래킹을 통해 주어진 n 길이만큼의 비밀번호 후보 순열을 만들고
선견지명 숫자가 포함되어 있는 경우만 카운트를 증가

🔽 코드 (C++)

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

int n, m; // 비밀번호의 길이, 선견지명으로 알게된 비밀번호에 들어가는 수의 개수 
int pwCount; // 가능한 모든 비밀번호의 개수
vector<int> partialPW;
vector<int> pw;

void search(int len) {
    if (len == n) {
        for (int i=0; i<m; i++) { // 선견지명 숫자 벡터 순회
            // 선견지명 숫자가 포함되지 않은 경우
            if (find(pw.begin(), pw.end(), partialPW[i]) == pw.end()) { 
                return;
            }
        }

        // 선견지명 숫자가 포함된 경우
        pwCount++; 
        return;
    }

    for (int i=0; i<10; i++) {
        pw.push_back(i);
        search(len+1);
        pw.pop_back(); // 백트래킹
    }
}

int main() {
    scanf("%d %d", &n, &m);
    
    int num;
    for (int i=0; i<m; i++) {
        scanf("%d", &num);
        partialPW.push_back(num);
    }

    search(0);

    printf("%d", pwCount);

    return 0;
}