[BOJ 백준] 17608번 1182번 17144번 (C++) | 백준 스터디 1주차

백준 스터디 1주차 (2022-03-15~2022-03-20 📚)

🥉 17608번 - 막대기

❔ 문제 바로가기

⭐ 풀이의 핵심

• 입력값 vector에 순서대로 push
• 오른쪽에서 N개의 막대기를 보았을 때 👉 vector의 마지막 원소부터 탐색
• (맨 오른쪽에 위치한 막대기는 항상 보이므로) vector의 맨 마지막 원소를 maxHeight 값으로 놓고 보이는 막대기 개수 하나 추가하고 맨 마지막에서 두번째 원소부터 탐색 시작
• maxHeight 보다 큰 값이 등장할 경우 보이는 막대기 개수 하나 추가하고 maxHeight 값 update

🔽 코드 (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_permutation활용하여 조합 구하기

  • next_permutation으로 뽑힌 순열의 순서를 무시하고 조합을 구하기 위해 isSelected라는 새로운 벡터에 N개의 원소 중 선택하려는 원소 개수 k만큼 1을, N-k만큼 0을 push
  • (🚨반드시 오름차순으로 0부터 넣든지, 다 넣은 후 sort 해주어야함)
  • next_permutaion을 돌린 후 isSelected에서 값이 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) 의 경우
    • 네 방향의 인접한 칸에 대해 확산 가능한 칸인지 체크
      • 인접한 칸의 인덱스 범위가 주어진 범위를 벗어남 또는 인접한 칸의 값이 -1
        👉 확산 불가능한 칸이므로 continue
      • 그 외
        👉 확산 가능한 칸이므로 nextRoom의 해당 칸에 (i,j)칸에 있는 먼지/5 값을 더해주고 확산 가능 칸의 개수를 하나 더해줌
    • 네 방향 다 돌고나면 카운트해준 확산 가능 칸의 개수를 대입하여 남은 미세먼지의 양을 nextRoom의 (i,j)에 더해줌
  • room 벡터를 전부 돌아서 원본(이전) room 상태가 필요 없어지면 room 벡터를 한 번에 nextRoom 벡터로 update
• cleanAir()
  • 아래 그림에서 노란색 칸에 있는 미세먼지 양은 공기청정기로 들어간 미세먼지는 모두 정화된다 조건에 따라 없어질 값이므로 0으로 초기화
  • 위쪽 ① -> ② -> ③ -> ④ -> 아래쪽 ① -> ② -> ③ -> ④ 순서대로 화살표 방향과 같이 칸에 들어있는 값들을 한 칸씩 당겨와줌
  • 초록색 칸에 있는 미세먼지를 당겨오는 로직을 따로 처리
    
• 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;
}