https://www.acmicpc.net/problem/18221

 

 

#문제 간단 정리

 

#문제 해결 방법

 

 문제그대로 구현하면된다

 

#전체 코드

#include <iostream>
#include <vector>
#include <utility>
#include <climits>
#include <cmath>

using namespace std;

vector<vector<int>> board;
pair<int, int> prof, sung;
int n;

// 학생을 세는 함수
bool CountingStudents(int ys, int ye, int xs, int xe, bool sameLine) {
    int count = 0;
    if (sameLine) {
        // 같은 행 또는 같은 열일 경우
        if (xs == xe) { // 같은 행
            for (int j = ys; j <= ye; j++) {
                if (board[xs][j] == 1) {
                    count++;
                }
            }
        } else { // 같은 열
            for (int i = xs; i <= xe; i++) {
                if (board[i][ys] == 1) {
                    count++;
                }
            }
        }
    } else {
        // 직사각형 내 모든 셀
        for (int i = xs; i <= xe; i++) { // 행 반복
            for (int j = ys; j <= ye; j++) { // 열 반복
                if (board[i][j] == 1) {
                    count++;
                }
            }
        }
    }
    return count >= 3;
}

int main() {
    cin >> n;
    board.resize(n, vector<int>(n));

    // 입력 받기 및 교수님과 성규의 위치 찾기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
            if (board[i][j] == 5) prof = {i, j};
            if (board[i][j] == 2) sung = {i, j};
        }
    }

    // 거리 계산 (제곱 거리 사용)
    int dist = pow(abs(sung.first - prof.first), 2) + pow(abs(sung.second - prof.second), 2);

    if (dist >= 25) {
        // 교수님과 성규의 위치를 기준으로 직사각형 정의
        int xs = min(prof.first, sung.first);
        int xe = max(prof.first, sung.first);
        int ys = min(prof.second, sung.second);
        int ye = max(prof.second, sung.second);

        // 같은 행 또는 같은 열인지 확인
        bool sameLine = false;
        if (prof.first == sung.first || prof.second == sung.second) {
            sameLine = true;
        }

        // 학생 수 세기
        if (CountingStudents(ys, ye, xs, xe, sameLine)) {
            cout << 1 << '\n';
            return 0;
        } else {
            cout << 0 << '\n';
            return 0;
        }
    } else {
        cout << 0 << '\n';
        return 0;
    }

    return 0;
}

 

 

 

https://www.acmicpc.net/problem/15812

#문제 간단 정리

bfs 나 혹은 브루트 포스로 풀 수 있는 문

 

 

#문제 해결 방법

 

우선 감염원 두개를 고르는 로직이 필요하고

 

그리고 감염원에서 각 마을까지의 최대 거리를 찾아주는 bfs를 사용해도 되고

 

한칸씩 전염되는 시뮬레이션을 만들어도 된다

 

나는 후자로 했다

 

이렇게 시뮬레이션 할때 중요한건

 

맵을 복사해서 상태를 감염 진행을 만드는게 중요하다 아래 코드에선 tempBoard라고 보면 될거다

 

 

#전체 코드

#include <iostream>
#include <vector>
#include <utility>
#include <climits>

using namespace std;

vector<vector<int>> board;
vector<vector<int>> tempBoard;
int n, m;

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

void contagion() {
    vector<vector<int>> nextBoard = tempBoard;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) {

            if (tempBoard[i][j] == 3) {

                for (int t = 0; t < 4; t++) {
                    int nx = j + dx[t];
                    int ny = i + dy[t];

                    if (0 <= ny && ny < n && 0 <= nx && nx < m) {
                        if (nextBoard[ny][nx] != 3) {
                            nextBoard[ny][nx] = 3;
                        }
                    }

                }

            }

        }
    }
    tempBoard = nextBoard;
}

bool isAllContagion() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 1 && tempBoard[i][j] != 3) {
                return false;
            }
        }
    }

    return true;
}

int main() {

    cin >> n >> m;

    board.resize(n, vector<int>(m));

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        for (int j = 0; j < s.length(); j++) {
            board[i][j] = s[j] - '0';
        }
    }

    vector<pair<int, int>> emptyCells;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 0) {
                emptyCells.push_back({ i, j });
            }
        }
    }

    int minSec = INT_MAX;

    for (size_t i = 0; i < emptyCells.size(); ++i) {
        for (size_t j = i + 1; j < emptyCells.size(); ++j) {
            pair<int, int> a = emptyCells[i];
            pair<int, int> b = emptyCells[j];

            // 복사후 감염원 설정
            tempBoard = board;
            tempBoard[a.first][a.second] = 3;
            tempBoard[b.first][b.second] = 3;

            int sec = 0;
            while (!isAllContagion()) {
                contagion();
                sec++;
            }
            minSec = min(sec, minSec);
        }
    }

    cout << minSec << '\n';

    return 0;
}

https://www.acmicpc.net/problem/24595

 

 

#문제 간단 정리

문제는 간단하니 번역은 안달아두겠다

 

대략 같거나 증가하는부분 같거나 감소하는 두 부분으로 이루어진 숫자를 만드는데

주어진 숫자와 같거나 작은수중에서 가장 큰 숫자를 만들면 된다

 

그리디 문제이다

 

 

#문제 해결 방법

 

우선 증가할때는 그대로 놔두는게 최선책이다

 

왜냐하면 앞자리수를 하나 내리게 되면 가장 손실이 크기 때문에

일단 증가하면 그대로 놔두고

 

감소할때가 관건인데 감소할 때 숫자가 작아진다면

계속 작아지게 놔두고

만약 작아지다가 작아진 값보다 큰 값이 나온다면 

그 이전 값으로 전부 통일시켜주면 된다

예를들어서

 

1234543291111

이라면 

123454322222

가 되는거다 왜냐면

91111

보다 

22222

가 작은 수가 되기 때문이다

이 부분에 주의하자

 

 

#전체 코드

#include <iostream>
#include <vector>
#include <unordered_map>
#include <utility>

using namespace std;



int main() {

    int t; cin >> t;

    while (t--) {
        string s;
        cin >> s;

        bool fall = false;
        char fix;
        bool isfix = false;
        for (int i = 1; i < s.length(); i++) {

            if (!fall) {
                if (s[i] - '0' < s[i - 1] - '0') {
                    fall = true;
                    fix = s[i];
                }
            }
            else {

                if (!isfix) {
                    if (s[i] - '0' > s[i - 1] - '0') { //더 커지는 순간 고정
                        s[i] = fix;
                        isfix = true;

                    }
                    else { //더 작아지면
                        //s[i] = s[i - 1];
                        fix = s[i];
                    }
                }
                else {
                    s[i] = fix;
                }

            }
        }

        cout << s << '\n';
    }

    

    return 0;
}

https://www.acmicpc.net/problem/15423

 

 

 

 

#한국어 번역

설명:

화폐 시스템 S는 실제 또는 가상의 화폐 시스템에서 동전의 값을 나타내는 고유한 양의 정수들의 유한 집합(비어있지 않은 집합)입니다. 예를 들어, 캐나다에서 사용되는 화폐 시스템은 {1, 5, 10, 25, 100, 200}으로, 1은 1센트 동전을 나타내고 200은 2달러(200센트)를 나타냅니다. 우리는 동전이 무한히 많다고 가정하며, S에는 항상 1이 포함된다고 가정합니다. 1이 포함된다는 것은 모든 양의 정수를 동전들의 합으로 표현할 수 있음을 보장합니다.

전 세계의 계산원들은 다음과 같은 문제에 직면합니다: 주어진 화폐 시스템과 고객에게 갚아야 할 양의 정수 금액이 있을 때, 정확히 그 금액을 맞추기 위해 필요한 최소 동전의 수는 얼마인가? 예를 들어, 캐나다의 계산원이 고객에게 83센트를 갚아야 한다고 가정합시다. 한 가지 가능한 방법은 25+25+10+10+10+1+1+1, 즉 8개의 동전을 주는 것이지만, 이는 최적의 방법이 아닙니다. 계산원은 25 + 25 + 25 + 5 + 1 + 1 + 1로 7개의 동전을 줄 수 있으며, 이 방법이 최적입니다.

다행히도, 캐나다 화폐 시스템은 탐욕 알고리즘이 항상 최적의 해를 제공하는 성질을 가지고 있습니다. 탐욕 알고리즘은 반복적으로 남은 금액보다 작거나 같은 가장 큰 값을 가진 동전을 선택하는 방식으로 진행합니다. 탐욕 알고리즘이 항상 최적의 해를 제공하는 화폐 시스템을 '정식(canonical)' 화폐 시스템이라고 부릅니다.

여러분의 도전 과제는 다음과 같습니다: 주어진 화폐 시스템 S = {c1, c2, ..., cn}에 대해 S가 정식인지 비정식(non-canonical)인지 판단하는 것입니다. 만약 S가 비정식이라면, 최소한 하나의 반례가 존재하며, 이는 탐욕 알고리즘으로 구한 동전 개수가 최적의 동전 개수보다 많아지는 양의 정수 x입니다.

입력:

입력은 하나의 경우로 구성됩니다. 첫 번째 줄에는 동전 종류의 수 n (2 ≤ n ≤ 100)이 주어집니다. 다음 줄에는 n개의 동전 값 c1 c2 ... cn이 공백으로 구분되어 주어지며, c1 = 1이고 c1 < c2 < ... < cn ≤ 10^6입니다.

출력:

화폐 시스템이 정식이면 "canonical"을, 비정식이면 "non-canonical"을 출력하세요.

 

 

#문제 간단 정리

그리디 + dp 를 구현하라

 

#문제 해결 방법

 

우선 딱 보면 알수 있겟지만

그리디를 구현하고

dp를 통한 최적해를 통해서

둘을 비교하면 얻을 수 있다는 것을 알 수 있다.

 

그리디는 쉽게 구현할 수 있으니 넘어가고

dp는 배낭문제와 같은데 

 

dp[i]는 금액 i을 만들기 위한 최소 동전 수

dp[i] = min(dp[i], dp[i - coins[j]] + 1);

 

의 점화식을 갖는다

 

그리고 

확인하는 최대 금액이 어째서

int max_x = coins[n-2] + coins[n-1]; 

인지가 중요한거 같은데 

지문에 

An example of a non-canonical coin system is {1, 3, 4}, for which 6 is a counterexample, since the greedy algorithm yields 4 + 1 + 1 (3 coins), but an optimal solution is 3 + 3 (2 coins). A useful fact (due to Dexter Kozen and Shmuel Zaks) is that if S is noncanonical, then the smallest counterexample is less than the sum of the two largest denominations.

라고 나와있는데 

"예를 들어, {1, 3, 4}라는 비정식(non-canonical) 화폐 시스템에서는 6이 반례(counterexample)가 됩니다. 탐욕 알고리즘을 사용하면 4 + 1 + 1, 즉 3개의 동전이 사용되지만, 최적의 해법은 3 + 3으로 2개의 동전만 필요합니다. Dexter Kozen과 Shmuel Zaks에 따르면, 화폐 시스템이 비정식이라면 가장 작은 반례는 두 개의 가장 큰 동전 값의 합보다 작다는 유용한 사실이 있습니다."

라고 잘 나와잇다.

 

#전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;


vector<int> coins;

int greedy(int value,vector<int> &coins) {

    int count = 0;
    int remaining = value;
   
    for (int i = coins.size() - 1; i >= 0; i--) {
        if (coins[i] <= remaining) {
            int num = remaining / coins[i];
            count += num;
            remaining -= coins[i] * num;

        }
        if (remaining == 0) {
            break;
        }



    }

    return count;

}



int main() {

    int n;
    cin >> n;

    coins.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }

    sort(coins.begin(), coins.end());

    int max_x = coins[n - 2] + coins[n - 1];

    vector<int> dp(max_x + 1, max_x + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= max_x; i++) {
        for (int j = 0; j < n; j++) {
            if (coins[j] <= i) {
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
            else {
                break;
            }
        }
    }

    bool isCanonical = true;

    for (int x = 1; x <= max_x; ++x) {
        int greedy_count = greedy(x, coins);
        if (greedy_count > dp[x]) {
            isCanonical = false;
            break;
        }

    }
    

    if (isCanonical) {
        cout << "canonical" << '\n';
    }
    else {
        cout << "non-canonical" << '\n';
    }

    return 0;
}

'[백준] > C++' 카테고리의 다른 글

백준 15812번 침략자 진아 [C++]  (0) 2024.10.02
백준 24595번 Rise and Fall [C++]  (0) 2024.10.01
백준 16405번 Birthday Boy [C++]  (1) 2024.09.21
백준 4040번 Polar Bear [C++]  (1) 2024.09.21
백준 31747번 점호 [C++]  (0) 2024.09.16

https://www.acmicpc.net/problem/16305

#한국어 번역

Bobby는 새 회사에 입사했고, 인사팀에서 그의 생일을 사무실 달력에 기록하도록 요청했습니다. Bobby the Birthday Boy는 특별하게 느끼고 싶어 합니다! 또한, Bobby the Birthday Boy는 주목받기 위해 거짓말을 하는 것을 꺼려하지 않습니다.

그는 사람들이 생일을 축하하지 않거나 케이크를 먹지 않은 기간이 길어질수록 새로운 생일이 찾아올 때 더 좋아한다는 것을 알아챘습니다. 그래서 가능한 한 긴 생일이 없는 기간이 막 끝난 시점에 자신의 생일을 정하고 싶어 합니다. 물론, 그는 동료들과 생일을 공유하고 싶지 않습니다.

Bobby가 가능한 한 특별하게 느낄 수 있도록 가짜 생일을 만들어 줄 수 있나요? Bobby는 윤년에 신경 쓰지 않습니다: 모든 해가 윤년이 아니며, 아무도 2월 29일에 생일이 없다고 가정할 수 있습니다. 만약 여러 날짜가 동일한 경우, Bobby는 현재 날짜인 10월 27일 직후에 오는 날짜를 선택하기로 결정했습니다. 이는 가능한 한 빨리 생일을 축하할 수 있기 때문입니다.

입력

첫 줄에 1 ≤ n ≤ 100, Bobby가 새 사무실에 있는 동료의 수가 주어집니다.

그 다음 n개의 줄이 이어지며, 각 줄은 한 동료에 해당합니다. 각 줄은 동료의 이름(최대 20개의 대소문자)과 생일 날짜가 공백으로 구분되어 주어집니다. 날짜는 mm-dd 형식입니다.

출력

Bobby가 선택한 가짜 생일 날짜(mm-dd 형식)를 출력하세요.

 

 

 

#문제 간단 정리

구현 + 시뮬레이션 문제

 

#문제 해결 방법

구현 시뮬레이션 문제이기 때문에 지문 그대로 구현하면 된다만..

 

예외 조건이 은근 있기 때문에 신경써야된다.

우선 입력에서 파싱을 사용해서 입력받아야되는걸 생각하고 

    // 동료들의 생일을 일수로 변환하여 저장
    for(int i = 0; i < n; i++) {
        string name, day;
        cin >> name >> day;
        int month = stoi(day.substr(0, 2));
        int d = stoi(day.substr(3, 2));
        dayto365.push_back(makeDays(month, d));
    }

우선 간격을 계산하기 위해서

월 일로 되어있는 걸

365일 기준으로 환산해주고

그걸 다시 월 일로 바꿔주는 함수를 만들자.

// 각 월의 일수 (비윤년 기준)
int daysInMonth[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 날짜를 일수로 변환하는 함수 (1~365)
int makeDays(int month, int day) {
    int result = 0;
    for(int i = 0; i < month - 1; i++) {
        result += daysInMonth[i];
    }
    result += day;
    return result;
}

// 일수를 "mm-dd" 형식으로 변환하는 함수
string day_to_date(int day_number) {
    int month = 1;
    while(day_number > daysInMonth[month - 1]) {
        day_number -= daysInMonth[month - 1];
        month++;
    }
    // 월과 일을 두 자리로 포맷팅
    string mm = (month < 10 ? "0" : "") + to_string(month);
    string dd = (day_number < 10 ? "0" : "") + to_string(day_number);
    return mm + "-" + dd;
}

 

여기서 중요한건 각 월을 배열로 저장해줘야 환산이 쉬워진다.

 

자 그렇다면 이렇게 환산한날들을 정렬해주고 

 

    // 생일을 정렬
    sort(dayto365.begin(), dayto365.end());

    // 연말을 넘어가는 경우를 처리하기 위해 첫 번째 생일에 365를 더해 추가
    dayto365.push_back(dayto365[0] + 365);

 

자 for 문을 돌면서 i-1 번째랑 비교해서 그 간격을 조사할건데

첫번째 인덱스 0 번은 i-1 번이 없기 때문에 365 를 더해서 뒤로 더해준다.

이렇게하면 전부 비교가 가능하다

int maxGap = -1;
    vector<int> candidates;

    // 가장 긴 간격을 찾고, 그 간격의 끝날(다음 생일 전날)을 후보로 추가
    for(int i = 1; i < dayto365.size(); i++) {
        int tempGap = dayto365[i] - dayto365[i - 1] - 1; // 생일 사이의 기간

        if(tempGap > maxGap){
            maxGap = tempGap;
            candidates.clear();

            int candidate_date = dayto365[i] - 1;
            if(candidate_date == 0) candidate_date = 365;
            // 동료의 생일과 겹치지 않는지 확인
            if(find(dayto365.begin(), dayto365.end() -1, candidate_date) == dayto365.end() -1){
                candidates.push_back(candidate_date);
            }
        }
        else if(tempGap == maxGap){
            int candidate_date = dayto365[i] - 1;
            if(candidate_date == 0) candidate_date = 365;
            if(find(dayto365.begin(), dayto365.end() -1, candidate_date) == dayto365.end() -1){
                candidates.push_back(candidate_date);
            }
        }
    }

 

자 이렇게 돌면서 만약에 같은 날짜가 생긴다면 

벡터에다 넣어서 동점인 날짜를 계산하기 위해 처리를 해준다

만약 겹치는 생일이 있으면 넣지 않는다 (이부분이 테스트케이스에 있는지 모르겠다.)

 

만약 현재 maxGap 과 같다면 벡터에 추가해서 나중에 처리하도록한다

 

다시 maxGap이갱신된다면 벡터를 clear해주고 넣어주자

// 현재 날짜인 10월 27일의 일수
    int the1027 = makeDays(10, 27);

    // 후보 날짜 중 10월 27일 이후의 날짜를 찾기 위한 처리
    vector<int> after1027;
    for(auto date : candidates){
        if(date > the1027){
            after1027.push_back(date);
        }
        else{
            after1027.push_back(date + 365); // 연말을 넘어가는 경우 처리
        }
    }

    int selected_date;
    if(!after1027.empty()){
        // 10월 27일 이후의 날짜 중 가장 빠른 날짜 선택
        selected_date = *min_element(after1027.begin(), after1027.end());
    }
    else{
        // 없다면 모든 후보 중 가장 빠른 날짜 선택
        selected_date = *min_element(candidates.begin(), candidates.end());
    }

 

이제 후보 날짜를 처리해 줄건데(동점인경우)

 

10/27일을 365단위로 환산해두고 일단

10/27일보다 작은경우 365를 더해서 벡터에 넣어준다.

int selected_date;
    if(!after1027.empty()){
        // 10월 27일 이후의 날짜 중 가장 빠른 날짜 선택
        selected_date = *min_element(after1027.begin(), after1027.end());
    }
    else{
        // 없다면 모든 후보 중 가장 빠른 날짜 선택
        selected_date = *min_element(candidates.begin(), candidates.end());
    }

    // 연말을 넘어간 날짜는 다시 1년으로 환산
    if(selected_date > 365){
        selected_date -= 365;
    }

    // 결과 날짜를 "mm-dd" 형식으로 변환하여 출력
    string result_date = day_to_date(selected_date);
    cout << result_date << endl;

그중에서 제일 작은걸 찾은 다음에

만약 365를 넘으면 빼서 정상화 해준뒤에

 

날짜 형식을 바꿔서  출력한다.

 

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// 각 월의 일수 (비윤년 기준)
int daysInMonth[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 날짜를 일수로 변환하는 함수 (1~365)
int makeDays(int month, int day) {
    int result = 0;
    for(int i = 0; i < month - 1; i++) {
        result += daysInMonth[i];
    }
    result += day;
    return result;
}

// 일수를 "mm-dd" 형식으로 변환하는 함수
string day_to_date(int day_number) {
    int month = 1;
    while(day_number > daysInMonth[month - 1]) {
        day_number -= daysInMonth[month - 1];
        month++;
    }
    // 월과 일을 두 자리로 포맷팅
    string mm = (month < 10 ? "0" : "") + to_string(month);
    string dd = (day_number < 10 ? "0" : "") + to_string(day_number);
    return mm + "-" + dd;
}

int main(){
    int n;
    cin >> n;
    vector<int> dayto365;

    // 동료들의 생일을 일수로 변환하여 저장
    for(int i = 0; i < n; i++) {
        string name, day;
        cin >> name >> day;
        int month = stoi(day.substr(0, 2));
        int d = stoi(day.substr(3, 2));
        dayto365.push_back(makeDays(month, d));
    }

    // 생일을 정렬
    sort(dayto365.begin(), dayto365.end());

    // 연말을 넘어가는 경우를 처리하기 위해 첫 번째 생일에 365를 더해 추가
    dayto365.push_back(dayto365[0] + 365);

    int maxGap = -1;
    vector<int> candidates;

    // 가장 긴 간격을 찾고, 그 간격의 끝날(다음 생일 전날)을 후보로 추가
    for(int i = 1; i < dayto365.size(); i++) {
        int tempGap = dayto365[i] - dayto365[i - 1] - 1; // 생일 사이의 기간

        if(tempGap > maxGap){
            maxGap = tempGap;
            candidates.clear();

            int candidate_date = dayto365[i] - 1;
            if(candidate_date == 0) candidate_date = 365;
            // 동료의 생일과 겹치지 않는지 확인
            if(find(dayto365.begin(), dayto365.end() -1, candidate_date) == dayto365.end() -1){
                candidates.push_back(candidate_date);
            }
        }
        else if(tempGap == maxGap){
            int candidate_date = dayto365[i] - 1;
            if(candidate_date == 0) candidate_date = 365;
            if(find(dayto365.begin(), dayto365.end() -1, candidate_date) == dayto365.end() -1){
                candidates.push_back(candidate_date);
            }
        }
    }

    // 현재 날짜인 10월 27일의 일수
    int the1027 = makeDays(10, 27);

    // 후보 날짜 중 10월 27일 이후의 날짜를 찾기 위한 처리
    vector<int> after1027;
    for(auto date : candidates){
        if(date > the1027){
            after1027.push_back(date);
        }
        else{
            after1027.push_back(date + 365); // 연말을 넘어가는 경우 처리
        }
    }

    int selected_date;
    if(!after1027.empty()){
        // 10월 27일 이후의 날짜 중 가장 빠른 날짜 선택
        selected_date = *min_element(after1027.begin(), after1027.end());
    }
    else{
        // 없다면 모든 후보 중 가장 빠른 날짜 선택
        selected_date = *min_element(candidates.begin(), candidates.end());
    }

    // 연말을 넘어간 날짜는 다시 1년으로 환산
    if(selected_date > 365){
        selected_date -= 365;
    }

    // 결과 날짜를 "mm-dd" 형식으로 변환하여 출력
    string result_date = day_to_date(selected_date);
    cout << result_date << endl;

    return 0;
}

 

'[백준] > C++' 카테고리의 다른 글

백준 24595번 Rise and Fall [C++]  (0) 2024.10.01
백준 15423번 Canonical Coin System [C++]  (1) 2024.09.22
백준 4040번 Polar Bear [C++]  (1) 2024.09.21
백준 31747번 점호 [C++]  (0) 2024.09.16
백준 7479번 Greatest Product [C++]  (0) 2024.09.13

https://www.acmicpc.net/problem/4040

#한국어 번역

문제

"Hey, John, John Conway의 Game of Life 알아?"

"직사각형 격자에 살아있는 셀과 죽은 셀이 있고, 모든 셀이 동시에 정해진 시계 틱에 따라 다음 세대의 셀 상태로 업데이트되는 그 게임 말하는 거지? 죽은 셀이 정확히 세 개의 살아있는 이웃을 가질 때 다음 세대에 살아있게 되고, 살아있는 셀이 이웃이 두 개 미만 또는 세 개 초과일 때 다음 세대에 죽게 되며, 다른 셀들은 상태가 변하지 않는 그 게임 말하는 거야?"

"응, 맞아. 내가 그걸 프로그래밍하려고 애쓰고 있는데..."

"대수롭지 않게 – 누구나 했잖아!"

"잠깐만, 내가 끝내게 – 극좌표 그래프 용지에서 작동하도록 프로그래밍하려고 해, 이렇게:"

"음. 진짜 곰처럼 보이네."

"나쁘지 않아 – 대부분의 셀은 Game of Life와 마찬가지로 여덟 개의 이웃을 가져. 외곽과 중심의 쐐기 모양 셀들이 까다로운데, 그건 처리할 방법을 찾았어. 반지름의 수가 짝수이면, 외곽과 내곽의 모든 셀은 여덟 개의 이웃을 가져: 링 위의 다섯 개의 일반 이웃과 가장 가까운 인접 링의 이웃, 그리고 그리드에서 지름상 반대편에 있는 셀, 그리고 그 셀의 왼쪽과 오른쪽 이웃. 예를 들어:"

"A의 이웃은 1번부터 8번까지의 셀이고, B의 이웃은 p부터 w까지의 셀이다."

"그렇다면 반지름의 수가 홀수일 때는 어떻게 해?"

"묻지 마."

입력

입력은 여러 개의 문제 인스턴스로 구성됩니다. 각 문제 인스턴스는 두 개의 양의 정수 m과 n으로 시작합니다. 여기서 m은 링의 수 (3 ≤ m ≤ 100), n은 반지름의 수 (6 ≤ n ≤ 100)이며, n은 항상 짝수입니다. 그 다음에 양의 정수 k와 k개의 서로 다른 쌍의 양의 정수가 주어지며, 이는 살아있는 셀의 위치를 나타냅니다. 첫 번째 정수는 링을 나타내며, 바깥 링부터 안쪽으로 0부터 시작합니다. 두 번째 정수는 해당 링에서의 셀 번호를 나타내며, 0부터 시계 방향으로 주어집니다 (시작 반지름은 임의의 고정된 반지름 선에서 시작). 그 다음에 비음수 정수 g (0 ≤ g ≤ 500)가 주어지며, 이는 세대 수를 나타냅니다. 마지막 테스트 케이스 뒤에는 두 개의 0이 주어집니다.

출력

각 테스트 케이스에 대해 테스트 케이스 번호와 다섯 개의 정수를 출력합니다: g번의 반복 후 살아있는 셀의 수, 첫 번째 살아있는 셀의 위치 (r1 c1), 마지막 살아있는 셀의 위치 (r2 c2). 여기서 첫 번째와 마지막은 살아있는 셀들을 링 번호와 셀 번호의 사전순으로 정렬했을 때의 첫 번째와 마지막을 의미합니다. 살아있는 셀이 없을 경우, 0 -1 -1 -1 -1을 출력합니다.

 

 

 

 

#문제 간단 정리

구현 + 시뮬레이션

사실상 지문 그대로 구현하면 된다.

 

#문제 해결 방법

 

문제이해:

이건 game of life 라는걸 다른버전으로 구현하는 것인데

아는사람이라면 반갑게 볼수 있다.

 

자 이 문제를 보자면

각 칸에 생존 혹은 사망 상태가 있고

시간이 지날때 주위에 생존이 2개미만 3개 초과면

사망하고

 

생존이 없는 칸에서 주위에 생존한게 3개 있다면

그 칸은 살아나게 된다.

 

그리고 다른 셀들은 상태가 변하지 않는다.

 

여기서 하나 주의 해야 될건 주위에 2개가있다면 생존상태가 그대로 유지된다는 점을 유의하자 

 

문제 설계:

 

자 구현문제이니 어떻게 구현할 것인지 설계하는게 중요하다

천천히 설계를 해 나가자

 

1.우선 각 라운드를 진행하기 위해서

시뮬레이팅 함수가 있으면 좋을것이다

simulated()

 

2.그리고 시뮬레이팅을 하려면 그 셀에 주위에 있는

셀을 카운팅하는 함수가 필요할 것이다.

findAround()

 

3. 그리고 출력하는데 있어서 첫번째 셀 그리고 마지막 셀을 찾아서 출력하는 함수가 필요할 것이다.

resultCells()

 

자 그렇다면 우리는

main(){

simulated(){

    findAround()

}

 

resultCells()

}

 

대략 이런식으로 구성될거라 생각 할 수 있고

 

polar를 구현할 자료구조로는

링이 하나씩 있고 링에 각 셀이 원형으로 포함되어있으니

이차원 벡터 혹은 배열이 좋을 것이다.

 

그리고 구현하기전에 생각해보자면 원형이기때문에 모듈러 연산을 활용하는 것이 좋을 것같다.

 

int m, n;

vector<pair<int, int>> cells;
vector<vector<int>> polar;


int main() {


    int t = 0;
    while (true) {

        cin >> m >> n;
        if (n == 0 && m == 0) {
            return 0;
        }
        t++;
        polar.assign(m ,vector<int>(n,0));

        int k;
        cin >> k;
        for (int i = 0; i < k; i++) {
            int ring, cell;
            cin >> ring >> cell;
            polar[ring][cell] = 1; //살아있음
        }

        int g;
        cin >> g;



        //g 만큼 시뮬레이션 진행
        simulate(g);

    

        //결과 출력
        resultCells(t);
    }
    

    return 0;
}

 

자 우선 입력과 메인함수 플로우를 보자면 이렇게 될 것이다.

 

그렇다면 시뮬레이팅 함수와 시뮬레이팅함수가 사용할 주변 셀 탐색 함수 를 만들자

 

void simulate(int g) {

    for (int p = 0; p < g; p++) {

        //변경을 저장할 임시 벡터
        vector<vector<int>> polarCopy = polar;
        //모든셀 조회
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 그 주위 살아있는 셀 몇개 인지 조회
                int aroundLiveCells = findAround(i, j);

                if (polar[i][j] == 1) { // 현재 셀이 살아있는 경우
                    if (aroundLiveCells < 2 || aroundLiveCells > 3) {
                        polarCopy[i][j] = 0;
                    }
                }
                else { // 현재 셀이 죽어있는 경우
                    if (aroundLiveCells == 3) {
                        polarCopy[i][j] = 1;
                    }
                }

                //cout << aroundLiveCells << ' ';

            }
        }


        polar = polarCopy;



    }

}

 

우선 시뮬레이팅 함수는 쉽게 구현 할 수 있다.

 

자그럼 탐색함수가 관건인데 모듈러 연산을 사용하는걸 주의하자

 

// 주위 셀 조사 함수
int findAround(int ring, int cell) {
    int cellCount = 0;
    int half = n / 2; // 반대편 셀을 찾기 위한 반

    // 링의 이전 링, 현재 링, 다음 링을 탐색 (-1, 0, 1)
    for (int i = -1; i <= 1; i++) { // 링 방향
        for (int j = -1; j <= 1; j++) { // 셀 방향
            if (i == 0 && j == 0) continue; // 자기 자신은 제외
            int nextRing = ring + i;
            int nextCell = (cell + j + n) % n; // 셀 번호는 모듈로 연산으로 순환
            if (nextRing >= 0 && nextRing < m) { // 링 범위 내인지 확인
                if (polar[nextRing][nextCell] == 1) {
                    cellCount++;
                }  
            }
            else {
                // 반대편 셀을 체크
                int oppositeCell = (nextCell + half + n) % n;
                if (polar[ring][oppositeCell] == 1) {
                    cellCount++;
                }
            }
        }
    }

    return cellCount;
}

 

 

자 문제의 조건에서 중요한건 가장 바깥쪽의 원이나 안쪽의 원은 만약에

그 외부 혹은 내부가 하나 없기때문에 반대쪽의 셀을 내부링 ,외부링 대신에 탐색하게 된다

if (nextRing >= 0 && nextRing < m)

그래서 nextRing이 벗어난 경우에는

            // 반대편 셀을 체크
                int oppositeCell = (nextCell + half + n) % n;
                if (polar[ring][oppositeCell] == 1) {
                    cellCount++;
                }

반대편 셀을 체크해주도록 하자

사실상 이부분이 구현이 끝낫다면 

 

void resultCells(int testCase) {
    int cellCount = 0;
    pair<int, int> first = { -1, -1 };
    pair<int, int> last = { -1, -1 };

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (polar[i][j] == 1) {
                cellCount++;
                if (first.first == -1) { // 첫 번째 생존 셀 설정
                    first = { i, j };
                }
                last = { i, j }; // 마지막 생존 셀 계속 업데이트
            }
        }
    }

    cout << "Case " << testCase << ": ";
    if (cellCount == 1) {
        cout << cellCount << " " << 0 << " " << 0<< " "
            << last.first << " " << last.second << "\n";
    }
    else if (cellCount > 0) {
        cout << cellCount << " " << first.first << " " << first.second << " "
            << last.first << " " << last.second << "\n";
    }
    else {
        cout << "0 -1 -1 -1 -1\n";
    }
}

 

출력함수는 쉽기때문에 여러방법으로 구현이 가능할 것이다.

 

#전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;


int m, n;

vector<pair<int, int>> cells;
vector<vector<int>> polar;

int findAround(int ring, int cell);
void simulate(int g) {

    for (int p = 0; p < g; p++) {

        //변경을 저장할 임시 벡터
        vector<vector<int>> polarCopy = polar;
        //모든셀 조회
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 그 주위 살아있는 셀 몇개 인지 조회
                int aroundLiveCells = findAround(i, j);

                if (polar[i][j] == 1) { // 현재 셀이 살아있는 경우
                    if (aroundLiveCells < 2 || aroundLiveCells > 3) {
                        polarCopy[i][j] = 0;
                    }
                }
                else { // 현재 셀이 죽어있는 경우
                    if (aroundLiveCells == 3) {
                        polarCopy[i][j] = 1;
                    }
                }

                //cout << aroundLiveCells << ' ';

            }
        }


        polar = polarCopy;



    }

}

// 주위 셀 조사 함수
int findAround(int ring, int cell) {
    int cellCount = 0;
    int half = n / 2; // 반대편 셀을 찾기 위한 반

    // 링의 이전 링, 현재 링, 다음 링을 탐색 (-1, 0, 1)
    for (int i = -1; i <= 1; i++) { // 링 방향
        for (int j = -1; j <= 1; j++) { // 셀 방향
            if (i == 0 && j == 0) continue; // 자기 자신은 제외
            int nextRing = ring + i;
            int nextCell = (cell + j + n) % n; // 셀 번호는 모듈로 연산으로 순환
            if (nextRing >= 0 && nextRing < m) { // 링 범위 내인지 확인
                if (polar[nextRing][nextCell] == 1) {
                    cellCount++;
                }  
            }
            else {
                // 반대편 셀을 체크
                int oppositeCell = (nextCell + half + n) % n;
                if (polar[ring][oppositeCell] == 1) {
                    cellCount++;
                }
            }
        }
    }

    return cellCount;
}

void resultCells(int testCase) {
    int cellCount = 0;
    pair<int, int> first = { -1, -1 };
    pair<int, int> last = { -1, -1 };

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (polar[i][j] == 1) {
                cellCount++;
                if (first.first == -1) { // 첫 번째 생존 셀 설정
                    first = { i, j };
                }
                last = { i, j }; // 마지막 생존 셀 계속 업데이트
            }
        }
    }

    cout << "Case " << testCase << ": ";
    if (cellCount == 1) {
        cout << cellCount << " " << 0 << " " << 0<< " "
            << last.first << " " << last.second << "\n";
    }
    else if (cellCount > 0) {
        cout << cellCount << " " << first.first << " " << first.second << " "
            << last.first << " " << last.second << "\n";
    }
    else {
        cout << "0 -1 -1 -1 -1\n";
    }
}

int main() {


    int t = 0;
    while (true) {

        cin >> m >> n;
        if (n == 0 && m == 0) {
            return 0;
        }
        t++;
        polar.assign(m ,vector<int>(n,0));

        int k;
        cin >> k;
        cells.clear();
        for (int i = 0; i < k; i++) {
            int ring, cell;
            cin >> ring >> cell;
            cells.push_back({ ring,cell });
            polar[ring][cell] = 1; //살아있음
        }

        int g;
        cin >> g;



        //g 만큼 시뮬레이션 진행
        simulate(g);

    

        //결과 출력
        resultCells(t);
    }
    

    return 0;
}

'[백준] > C++' 카테고리의 다른 글

백준 15423번 Canonical Coin System [C++]  (1) 2024.09.22
백준 16405번 Birthday Boy [C++]  (1) 2024.09.21
백준 31747번 점호 [C++]  (0) 2024.09.16
백준 7479번 Greatest Product [C++]  (0) 2024.09.13
백준 16624번 Bingo Ties [C++]  (0) 2024.09.13

 

 

 

 

#문제 간단 정리

 

#문제 해결 방법

 

  • 진료과 필터링:
    • WHERE 절을 사용하여 MCDP_CD가 'CS'(흉부외과) 또는 'GS'(일반외과)인 의사들만 선택합니다.
      • 이는 문제에서 요구한 "진료과가 흉부외과 또는 일반외과인 의사"를 조회하기 위한 것입니다.
  • 필요한 컬럼 선택 및 날짜 형식 지정:
    • SELECT 절에서 의사의 이름(DR_NAME), ID(DR_ID), 진료과 코드(MCDP_CD), 고용일자(HIRE_YMD)를 선택합니다.
    • HIRE_YMD는 DATE_FORMAT 함수를 사용하여 'YYYY-MM-DD' 형식으로 변환합니다.
      • 이는 출력되는 날짜가 예시와 동일한 포맷을 가지도록 하기 위함입니다.
  • 결과 정렬:
    • ORDER BY 절을 사용하여 결과를 정렬합니다.
      • 먼저 HIRE_YMD DESC로 고용일자를 기준으로 내림차순 정렬하여 최근에 고용된 의사가 먼저 나오도록 합니다.
      • 고용일자가 같은 경우 DR_NAME ASC로 의사 이름을 기준으로 오름차순 정렬합니다.

 

 

 

#전체 코드

 

SELECT
    DR_NAME,DR_ID,MCDP_CD,DATE_FORMAT(HIRE_YMD, '%Y-%m-%d') AS HIRE_YMD

FROM
    DOCTOR
    
WHERE MCDP_CD = 'CS' OR MCDP_CD = 'GS'

ORDER BY HIRE_YMD DESC,DR_NAME ASC;

 

ROUND 함수는 SQL에서 숫자 값을 지정된 소수 자리까지 반올림하는 데 사용됩니다. 일반적인 구문은 다음과 같습니다:

ROUND(number, decimal_places)
  • number: 반올림할 숫자 값입니다.
  • decimal_places: 반올림할 소수 자릿수입니다.

예시를 통해 설명하겠습니다:

  • ROUND(123.456, 2)는 123.46이 됩니다. 소수 둘째 자리까지 반올림하므로 셋째 자리인 6이 반올림 기준이 됩니다.
  • ROUND(123.456, 0)는 123이 됩니다. 소수 첫째 자리에서 반올림하여 정수 부분만 남습니다.
  • ROUND(123.456, -1)은 120이 됩니다. 소수점 왼쪽 첫째 자리에서 반올림합니다.

 

 

#전체 코드

SELECT 
    ROUND(AVG(DAILY_FEE), 0) 
FROM 
    CAR_RENTAL_COMPANY_CAR
WHERE 
    CAR_TYPE = 'SUV';

 

 

https://www.acmicpc.net/problem/31747

 

 

#문제 간단 정리

 

2학년과 1학년이 섞인 줄에서

가장 앞에있는 2학년과 1학년을 

하나씩 없에는 기능을 구현하는

 

구현 + 시뮬레이션 문제

 

 

#문제 해결 방법

 

우선 나이브하게 

그냥 1학년과 2학년을 k만큼 탐색해서

벡터에서 제거해주는 나이브한 로직을 생각 해 낼 수 있는데

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {

    int n, k;
    cin >> n >> k;

    vector<int> line(n);

    for (int i = 0; i <n; i++) {
        cin >> line[i];
    }

    int time = 0;
    
    while (!line.empty()) {
        bool grade1 = false;
        bool grade2 = false;
        int grade1Index = 0;
        int grade2Index = 0;

        int checkLength = line.size();
        checkLength = min(k, checkLength);

        for (int i = 0; i < checkLength; i++) {
            if (line[i] == 1 && grade1 == false) {
                grade1Index = i;
                grade1 = true;
            }
            if (line[i] == 2 && grade2 == false) {
                grade2Index = i;
                grade2 = true;
            }

        }
        if (grade1 && grade2) {
            if (grade1Index < grade2Index) {
                line.erase(line.begin() + grade2Index);
                line.erase(line.begin() + grade1Index);
            }
            else {
                line.erase(line.begin() + grade1Index);
                line.erase(line.begin() + grade2Index);
            }
        }
        else if (grade2) {
            line.erase(line.begin() + grade2Index);
        }
        else if (grade1) {
            line.erase(line.begin() + grade1Index);
        }
           
;
        time++;
    }

    cout << time << '\n';

    return 0;
}

 

벡터에서 제거하는 부분에서도 시간초과가 날 수 있지만

 

그전에 간단하게 만약 k = n 이라고 하게 되면 

항상 n개를 탐색하게 되어서 매우 시간복잡도 가 크게 된다

 

 

때문에 나는

1학년과 2학년의 위치를

덱에 넣고

 

 

얼마만큼 빠져나간지 알도록 인덱스를 사용하였다

현재 줄에서 빠져나간 만큼 인덱스를 올려서 인덱스를 참조하도록 하였다.

 

여기서 1학년 덱과 2학년 덱을 조사해서 맨 앞에 있는 값이 

인덱스 + k 의 값 이하의 값을 가지고 있다면 

덱에서  pop 해주고 인덱스를 올려 줬다.

 

이렇게 남은 1학년과 2학년의 숫자와

줄의 길이를 빠르게 추적 가능하다

 

정확히 이런 기능을 어떻게 구현할지 물어보는 문제라고 볼 수 있겠다.

 

아 물론 덱을 안쓰고 벡터를 역순으로 집어 넣는다던가 하는 식으로 덱을 안써도 할 수 있겟지만

직관적으로 풀려고 덱을 사용하였다.

 

#전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
#include <deque>;

using namespace std;

int main() {

    int n, k;
    cin >> n >> k;

    deque<int> line(n);
    deque<int> grade1;
    deque<int> grade2;
    int lineSize = line.size();

    for (int i = 0; i < n; i++) {
        cin >> line[i];
 
        if (line[i] == 1) {
            grade1.push_back(i);
        }
        else {
            grade2.push_back(i);
        }
    }


    int time = 0;
    int index = 0;

    while (index < line.size()) {


        //남은 인덱스 확인
        int checkLength = index + k - 1;
        checkLength = min(lineSize -1 , checkLength);

        if (!grade1.empty() && grade1.front() <= checkLength) {
            index++;
            grade1.pop_front();
        }
        if (!grade2.empty() && grade2.front() <= checkLength) {
            index++;
            grade2.pop_front();
        }

        time++;
    }

    cout << time << '\n';

    return 0;
}

https://www.acmicpc.net/problem/7497

 

 

#문제 간단 정리

 

N 이 주어지고 

N 이하의 숫자들에서

 

각 자리수를 곱햇을때 가장 커지는 숫자를 찾는 문제

 

#문제 해결 방법

 

N 이하의 숫자들의 자리수의 곱의 최대라는 말은

4876이면 4 *  8 * 7 * 6  이렇게 곱할 수 있고

4876 이하의 숫자인 3999도

곱해서 3 * 9 * 9 * 9 를 곱해서 최대값을 찾을 수 있다.

 

여기서 쉽게 생각 할 수 있는건 9를 최대한 많이 만든다는건데

 

일단 어떤 자리수를 1내리면 그 뒤에 숫자들은 전부 9로 만들수 있다.

 

때문에 각 자리수를 한번씩 1 내리고 그 뒤에수를 전부 9로 만들어 주면서

 최대값을 찾아주면 된다.

 

#전체 코드

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

typedef long long ll;

int main() {



    string s;
    cin >> s;

    ll startMax = 1;

    for (int i = 0; i < s.length(); i++) {
        
        if (s[i] - '0' != 0) {
            startMax *= s[i] - '0';
        }
    }



    for (int i = 0; i < s.length(); i++) {

        ll tempMax = 1;
        if (s[i] - '0' - 1 != 0) { //1 내려서 0이면 곱하지 않고 넘어감
            tempMax *= s[i] - '0' - 1;
        }

        for (int j = i + 1; j < s.length(); j++) { //이후 자리수들 전부 9로 만들기

            tempMax *= 9;

        }

        for (int t = 0; t < i; t++) { //이전자리수들 곱해주기
            if(s[t] - '0' != 0)
                tempMax *= s[t] - '0';

        }

        startMax = max(tempMax, startMax);
    }

    cout << startMax << '\n';

    return 0;
}

'[백준] > C++' 카테고리의 다른 글

백준 4040번 Polar Bear [C++]  (1) 2024.09.21
백준 31747번 점호 [C++]  (0) 2024.09.16
백준 16624번 Bingo Ties [C++]  (0) 2024.09.13
백준 9764번 서로 다른 자연수의 합 [C++]  (0) 2024.09.13
백준 4358번 생태학 [C++]  (0) 2024.09.13

+ Recent posts