[BOJ白俊]17608号1182号17144号(C++)|白俊学習1週目

白駿学習1週目(2022年03月15日から2022年03月20日まで)📚)

🥉 17608号-棒

❔问题的短片

解の核心

入力値ベクトルを順次プッシュ

오른쪽에서 N개의 막대기를 보았을 때 👉 vectorの最後の要素から

へのナビゲートを開始

(常に右端のバーが見える)ベクトルの最後の要素をmaxHeight値として可視バー数を追加し、最後の要素から2番目の要素へのナビゲート

を開始する.

より大きいmaxHeightの値が現れると、可視ストライプ数が追加され、maxHeightの値

が更新される.

🔽 コード(C+)

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

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

    vector<int> v;
    int num;
    for (int i=0; i<N; i++) {
        scanf("%d", &num);
        v.push_back(num);
    }

    // maxHeight: 오른쪽~현재 지점 중 가장 높은 막대기
    // 막대기의 높이 h의 범위 1 ≤ h ≤ 100,000 이므로 0으로 초기화
    int maxHeight = 0;
    int answer = 0; 
    for (int i=N-1; i>=0; i--) { // 맨 오른쪽부터 탐색
        if (v[i] > maxHeight) {
            answer++;
            maxHeight = v[i];
        }
    }

    // 출력
    printf("%d", answer);

    return 0;
}

🥈 1182-部分数列の合計

❔问题的短片

解の核心

📌 リファレンス
C++クリーンアップに役立つライブラリと関数next permutation|ショートカット

N個の数字の中で、k(1,2,3,...N)個の数字の組み合わせを求めます
📌 注意:next置換を使用して組合せを求める

next置換として選択するシーケンスの順序は無視され、isSelectedという新しいベクトルでは、n個の要素の個数kは1、n-kは0はpushは

である.

(🚨0から昇順に入れるか、全部入れて並べ替えなければならない)

.

next persionを返すと、isSelectedの値が1インデックスと同じソースベクトルの値

のみ選択されます.

選択された組合せのすべての要素に1つの値がSである場合、

の数が求められる.

🔽 コード(C+)

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

int main() {
    // 입력
    int N, S;
    scanf("%d %d", &N, &S);

    vector<int> v;
    int num;
    for (int i=0; i<N; i++) {
        scanf("%d", &num);
        v.push_back(num);
    }

    int answer = 0;
    for (int i=1; i<=N; i++) { // 조합(부분수열)으로 선택할 원소 개수 1~N개
        vector<int> isSelected; // 선택할 원소 개수만큼 1 push
        for (int j=0; j<N-i; j++) { isSelected.push_back(0); }
        for (int j=0; j<i; j++) { isSelected.push_back(1); }
           
        // next_permutation을 활용한 조합(부분수열) 구하기
        do {
            int sum = 0;
            for (int j=0; j<N; j++) {
                if (isSelected[j]) { sum += v[j]; }
            }

            // cf) 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구할 것
            if (sum == S) { answer++; }
        } while (next_permutation(isSelected.begin(), isSelected.end()));
    }

    // 출력
    printf("%d", answer);

    return 0;
}

🥇 17144号-スモッグこんにちは!

❔问题的短片

解の核心

roomベクトルに値を入力すると、空気清浄機の位置が

列は常に1に固定するので、行

のみが格納.

cleanerRow[0]空気清浄機の上にあり、cleanerRow[1]空気清浄機の下にある

.

spreadDust()

확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다 👉 既存のroomベクトルを元のベクトルとして保持し、nextroomベクトルを個別に宣言して、拡散後の状態の

を含む.

roomベクトルが回転し、ほこりのあるセル(i,j)

隣接する4方向のセルが分散可能なセルであるかどうかを確認します.

隣接セルのインデックス範囲が指定範囲を超えているか、隣接セルの値が-1です.
👉 セルを拡散できないためcontinue

👉 拡散可能な格子であるため、nextRoomの対応する格子に(i,j)格子中の塵埃/5値を加え、さらに1つの拡散可能な格子数

を加える.

は4方向を回転した後、カウントされた拡散可能な格子数をnextRoomの(i,j)に代入し、残りのスモッグ量をnextRoomの(i,j)に

加算.

roomベクトルをすべて迂回し、元の(前の)room状態を必要としない場合、roomベクトルをnextRoomベクトル

に一度に更新する.

cleanAir()
図

では、黄色格子中のスモッグ量は공기청정기로 들어간 미세먼지는 모두 정화된다の条件に従って消失するので、0

に初期化する.

上辺①->②->③->④->下辺①->②->③->④矢印の方向にセルの値を1段ずつ1段ずつ引き寄せる

.
独立処理

緑色格子中の微塵

SpreadDust()とcleanAir()をそれぞれT回運転した後、総残塵量

を算出する.

🔽 コード(C+)

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

int R, C, T;
int totalDust = 0; // T초 후 남아있는 미세먼지의 양
vector<vector<int>> room(50, vector<int>(50));
vector<int> cleanerRow; // 공기청정기의 행 인덱스

// 위쪽 오른쪽 아래쪽 왼쪽
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

bool isOutOfRange(int row, int col) {
    if (row < 0 || row >= R || col < 0 || col >= C) { 
        return true;
    }
    return false;
}

void spreadDust() {
    // 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
    vector<vector<int>> nextRoom(50, vector<int>(50, 0));
    nextRoom[cleanerRow[0]][0] = -1;
    nextRoom[cleanerRow[1]][0] = -1;

    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            int dust = room[i][j];
            if (dust == -1 || dust == 0) { continue; }

            // (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
            int spreadCount = 0; // 확산이 일어난 방향의 개수
            for (int k=0; k<4; k++) {
                int adjRow = i + dr[k];
                int adjCol = j + dc[k];

                // 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
                if (isOutOfRange(adjRow, adjCol) || room[adjRow][adjCol] == -1) { continue; }

                // 확산되는 양은 Ar,c/5이고 소수점은 버린다.
                nextRoom[adjRow][adjCol] += dust / 5;
                spreadCount++;
            }

            // (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
            nextRoom[i][j] += (dust - dust / 5 * spreadCount);
        }
    }

    room = nextRoom;
}

void cleanAir() {
    // 공기청정기로 들어간 미세먼지는 모두 정화된다.
    room[cleanerRow[0]-1][0] = 0;
    room[cleanerRow[1]+1][0] = 0;

    // 위쪽 공기청정기의 바람은 반시계방향으로 순환한다.
    for (int i=cleanerRow[0]-1; i>0; i--) { room[i][0] = room[i-1][0]; } // ↓
    for (int i=0; i<C-1; i++) { room[0][i] = room[0][i+1]; } // ←
    for (int i=0; i<cleanerRow[0]; i++) { room[i][C-1] = room[i+1][C-1]; } // ↑
    for (int i=C-1; i>1; i--) { room[cleanerRow[0]][i] = room[cleanerRow[0]][i-1]; } // →
    room[cleanerRow[0]][1] = 0;

    // 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
    for (int i=cleanerRow[1]+1; i<R-1; i++) { room[i][0] = room[i+1][0]; } // ↑
    for (int i=0; i<C-1; i++) { room[R-1][i] = room[R-1][i+1]; } // ←
    for (int i=R-1; i>cleanerRow[1]-1; i--) { room[i][C-1] = room[i-1][C-1]; } // ↓
    for (int i=C-1; i>1; i--) { room[cleanerRow[1]][i] = room[cleanerRow[1]][i-1]; } // →
    room[cleanerRow[1]][1] = 0;
}

void getTotalDust() {
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            if (room[i][j] == -1 ||  room[i][j] == 0) { continue; }
            totalDust += room[i][j];
        }
    }
}

int main() {
    // 입력
    scanf("%d %d %d", &R, &C, &T);
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            scanf("%d", &room[i][j]);

            // 공기청정기 위치 저장
            // 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 
            if (room[i][j] == -1) {
                cleanerRow.push_back(i);
            }
        }
    }

    // T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양 구하기
    for (int i=0; i<T; i++) {
        // 1초 동안 일어나는 일 1. 미세먼지 확산 2.공기청정기 작동
        spreadDust();
        cleanAir();
    }
    getTotalDust();

    printf("%d", totalDust);

    return 0;
}