240227: 공주님의 정원 문제와 LIS 복습, 조합론 나머지 합 문제

2024-02-27

2차 공부 계획

• 2월 25일 - 문제풀이집 1 풀이 (RGB 거리 ~ 오르막 수) 8문제 ✅ 2024-02-26
• 2월 26일 - 문제풀이집 1 풀이 (오르막 수 ~ N과 M 시리즈) 10문제 ✅ 2024-02-26
• 2월 27일 - 문제풀이집 1 완성. (N과 M 시리즈 ~ 끝) 8문제 ✅ 2024-02-27
• 2월 28일 - SW 문제풀이집 2 되는대로 풀기.. 총 70문제 🤯
• 2월 29일 - SW 문제풀이집 2
• 3월 1일 - SW 문제풀이집 2
• 3월 2일 - SW 문제풀이집 2

가장 긴 증가하는 부분 수열 (11053)

예전에 인상깊어했던 LIS 문제. DP 방식으로 푸는 문제다.
더 효율적으로 이분탐색의 lower_bound로도 풀 수 있다.

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

// 교육적 의미로 구현 (이분탐색을 이용한 LIS)
int LIS(const vector<int> &nums) {
    vector<int> lis;
    for (int num : nums) {
        auto it = lower_bound(lis.begin(), lis.end(), num);
        if (it == lis.end())
            lis.push_back(num);
        else
            *it = num;
    }
    return lis.size();
}

int main() {
    int N;
    cin >> N;
    vector<int> dp(N, 1);
    vector<int> lis(N);
    for (int i = 0; i < N; ++i) {
        cin >> lis[i];
    }

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (lis[j] < lis[i])
                dp[i] = max(dp[j] + 1, dp[i]);
        }
    }

    cout << *max_element(dp.begin(), dp.end());
    // cout << LIS(lis); 
    return 0;
}

---

유기농 배추 (1012)

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력하시오.

DFS를 통해 배추 그룹, 단 그룹 기준은 상하좌우 인접 (dx, dy배열로 관리)로 두고 가능한 각 그룹을 맵에서 지워가면서 개수를 세는 간단한 방식으로 구현해서 풀었다.

DFS , BFS 문제는 이제 밥먹듯이 푸는 것 같다. 실버 문제만.
그래도 이 정도면 그래프와 순회 부분은 나름대로 견고한듯 ..

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

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
vector<vector<int>> map;
int M, N, K; // 가로, 세로

void dfs(int x, int y) {
    map[y][x] = 0;
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
            if (map[ny][nx] == 1)
                dfs(nx, ny);
        }
    }
}

int main() {
    int TC;
    cin >> TC;
    while (TC--) {
        cin >> M >> N;
        map.assign(N, vector<int>(M, 0));
        cin >> K; // 배추 개수
        for (int i = 0; i < K; ++i) {
            int x, y;
            cin >> x >> y;
            map[y][x] = 1;
        }
        int counter = 0;
        // DFS 돌리고 지렁이수 계산
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < M; ++x) {
                if (map[y][x] == 1) {
                    ++counter;
                    dfs(x, y);
                }
            }
        }

        cout << counter << "\n";
    }
    return 0;
}

---

수 찾기 (1920)

매우 쉬운 이분 탐색, 혹은 set 자료구조를 사용하는 문제.
이분 탐색의 경우는 직접 구현하거나 std::binary_search를 사용해도 되고
나는 set으로 풀었는데, set은 중복을 허용하지 않고 내부적으로 균형 이진 탐색 트리를 사용하기 때문에 검색, 삽입, 삭제등의 연산에 O(log n)시간에 수행할 수 있다.

입력된 값을 죄다 set에 넣고. set.find()!=set.end() 조건으로 찾으면서 풀었다.

#include <iostream>
#include <set>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    set<int> s;
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int temp;
        cin >> temp;
        s.insert(temp);
    }

    int M;
    cin >> M;
    for (int i = 0; i < M; ++i) {
        int temp;
        cin >> temp;
        if (s.find(temp) != s.end()) {
            cout << "1\n";
        } else {
            cout << "0\n";
        }
    }
    return 0;
}

숫자 카드 (10815)

이전 문제와 거의 동일한 문제. 거의 동일 코드로 풀었다. 매우 쉬웠다 (실버 4~5)
set을 써도 되고, 해시, 맵, 이분탐색 아무거나 써도 풀린다.

---

중요한 팁 !

• INT_MAX엔 (~0U >> 2); 를 쓰자.
  0U는 Unsigned Int 0 이라는 뜻이다. 즉 0의 값인 부호없는 정수형을 선언한다. 이때 모든 32개의 비트는 0이다. 이걸 ~ 로 반전하면 모든 부호가 1이 된다. 즉 Unsigned Int가 가질 수 있는 최댓값이 된다. 이때 오른쪽으로 시프트 두번을 하면, 4로 나누는 것과 동일하다. 이 값은 Signed Int 최댓값의 반절이며, 자기 자신을 더하는 TC가 들어와도 오버플로우가 나지 않는다. (특히 최단거리 알고리즘에서)

따라서, 외우기 쉬운 형태에 부작용도 제일 적은 초기화 방법 : ~0U >> 2를 쓰자.

---

연산자 끼워넣기 (14888)

이 문제는 N개의 수로 이루어진 수열에서 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 문제다.

약간의 DFS 심화 문제다. 실버 1인데 아주 무난하게 풀었다. 다른 알고리즘과 비교했을 때 나는 DFS + BFS를 잘하는 것 같다.. 🥺

딱히 고민한 것 없이 풀었다. 연산자 개수를 배열로 관리하고 DFS 백트래킹하면서 풀었다

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

vector<int> nums;
vector<int> operators(4);
int N;

int min_answer = (~0U >> 2);
int max_answer = (~0U >> 1) * -1;

void dfs(int depth, int current, vector<int> &operators) {
    if (depth == N) {
        min_answer = min(min_answer, current);
        max_answer = max(max_answer, current);
        return;
    }

    for (int i = 0; i < 4; ++i) {
        if (operators[i] > 0) { // 연산자가 사용 가능하다면
            operators[i] -= 1;

            if (i == 0) // 덧셈
                dfs(depth + 1, current + nums[depth], operators);
            else if (i == 1) // 뺄셈
                dfs(depth + 1, current - nums[depth], operators);
            else if (i == 2) // 곱셈
                dfs(depth + 1, current * nums[depth], operators);
            else if (i == 3) // 나눗셈
                dfs(depth + 1, current / nums[depth], operators);

            operators[i] += 1;
        }
    }
}

int main() {
    cin >> N;
    nums.assign(N, 0);
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }

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

    dfs(1, nums[0], operators);

    cout << max_answer << "\n" << min_answer;
    return 0;
}

---

스타트와 링크 (14889)

교육적인 문제.

스타트와 링크는 각 사람들이 조합됐을때의 시너지 능력치 2D 배열이 주어지고, 사람 수 N이 주어졌을 때. (단 N은 항상 짝수 <= 20) 가장 팀간의 능력치 차이를 최소로 하는 값을 찾는 백트래킹 문제.

이 문제는 간단한 DFS + 백트래킹 문제지만 한가지의 최적화 방법이 있다.
바로 DFS 내부의 조합 탐색 for문에서, 아래와 같이 현재 선택된 사람을 인자로 넘겨서, 다음 for문에선 이전에 선택된 사람 다음의 사람부터 고려하도록 하는 것이다.

    for (int i = selected; i <= N; ++i) {
        if (!visited[i]) { // 방문하지 않았다면
            visited[i] = true;
            team.push_back(i);
            dfs(depth + 1, team, visited, i);
            visited[i] = false;
            team.pop_back();
        }
    }

어차피 두 사람의 시너지라는 것은 1 + 2든 2 + 1이든 동일하다. 따라서 1 + 2를 계산했으면 2 + 1을 다시 선택해서 계산하지 않도록 하기 위해서, 현재 선택한 사람을 다음 재귀의 인자로 보낸다. 이것을 통해 계산량을 기하급수적으로 감소시킬 수 있다. 이 최적화를 처음엔 생각하지 못해서 TLE를 받았다.

다음부턴, 특히 DFS + 백트래킹을 할 때 문제의 요구사항에 맞는 계산 로직을 신경써야겠다. 이런 발상은 처음 해보는 것 같다.

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

vector<vector<int>> S;
int N;
int answer = (~0U >> 2);

int calculate(const vector<int> &team) {
    int score = 0;
    for (int i = 0; i < team.size(); ++i) {
        for (int j = 0; j < team.size(); ++j) {
            score += S[team[i]][team[j]];
        }
    }
    return score;
}

void dfs(int depth, vector<int> &team, vector<bool> &visited, int selected) {
    if (depth == N / 2) {
        vector<int> team_compare;
        for (int i = 1; i <= N; ++i) {
            if (find(team.begin(), team.end(), i) == team.end())
                team_compare.push_back(i);
        }
        answer = min(answer, abs(calculate(team) - calculate(team_compare)));
        return;
    }

    for (int i = selected; i <= N; ++i) {
        if (!visited[i]) { // 방문하지 않았다면
            visited[i] = true;
            team.push_back(i);
            dfs(depth + 1, team, visited, i);
            visited[i] = false;
            team.pop_back();
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N;
    S.assign(N + 1, vector<int>(N + 1, 0));

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            cin >> S[i][j];
        }
    }
    vector<int> team;
    vector<bool> visited(N + 1, false);
    dfs(0, team, visited, 1);
    cout << answer;

    return 0;
}

---

쉬운 계단수 (10844)

쉬운 계단 수 문제는 이전 문제에서도 풀었던 중복 문제다.
쉽게 풀었는데 오버플로우를 적절하게 관리하지 못해서 처음엔 WA가 났다.
std::accumulate 함수를 쓰고 있었는데, 여기서 시작 인자를 int형으로 준 것도 문제였고. 0LL 로 줘야 안전하다.
그리고 accumulate에서는 각 단계마다 MOD를 적용할 수 없었다.

따라서 그냥 for문으로 대체하고 MOD를 적용시켰다... 괜히 STL 써보겠다고 쓴건데. 조금 더 생각하고 쓸 걸.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;
#define MOD 1'000'000'000
typedef long long ll;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector<vector<ll>> dp(N + 1, vector<ll>(10, 0));
    for (int i = 1; i <= 9; ++i) {
        dp[1][i] = 1;
    }
    for (int i = 2; i <= N; ++i) {
        for (int j = 0; j <= 9; ++j) {
            if (j == 0) {
                dp[i][j] += dp[i - 1][j + 1] % MOD;
            } else if (j == 9) {
                dp[i][j] += dp[i - 1][j - 1] % MOD;
            } else {
                dp[i][j] += dp[i - 1][j - 1] % MOD + dp[i - 1][j + 1] % MOD;
            }
            dp[i][j] %= MOD;
        }
    }

    ll answer = 0;
    for (int i = 0; i <= 9; ++i) {
        answer += dp[N][i];
        answer %= MOD;
    }
    cout << answer;
    return 0;
}

---

가장 긴 바이토닉 부분 수열 (11054)

가장 긴 바이토닉 부분 수열 문제는 LIS와 LDS를 계산해서
S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN 식의 수열의 최대 길이를 구하는 문제다.

LIS와 LDS는 DP를 이용해서 계산하는데, 바이토닉 부분 수열은 왼쪽에서 오른쪽으로 증가하고(LIS), 오른쪽에서 왼쪽으로 감소하는(LDS) 수열이기 때문에. LIS는 정방향으로 계산하고 LDS는 역방향으로 계산해야 한다.

왜 거꾸로 계산해야 하는가?
LDS를 만약 정방향으로 계산한다면, 각 지점에서 시작하여 오른쪽으로 얼마나 긴 감소 수열을 형성할 수 있는지를 찾는 것이 아니라, 각 지점을 끝으로 하는 감소 수열의 길이를 찾게 된다. 이는 바이토닉 수열을 찾는 목적에 부합하지 않다.

따라서, LIS는 각 지점을 기준으로 왼쪽으로 얼마나 긴 증가 수열을 형성할 수 있는 지 메모하고, LDS는 각 지점을 기준으로 오른쪽으로(역방향) 얼마나 긴 감소 수열을 형성할 수 있는 지 메모한다.

이제 각 지점에 대해 LIS와 LDS의 값을 더 한 것의 최댓값을 찾으면, 바이토닉 부분 수열의 최댓값을 찾을 수 있다.

주의 해야 할 점은 1 2 3 2 1 이라고 할 때, LIS 는 1 2 3 LDS는 3 2 1 로 중간 부분 3 이 겹치게 된다. 따라서 MAX(각 지점 LIS + LDS) - 1 로 계산한다.

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

using namespace std;
int main() {
    int N;
    cin >> N;
    vector<int> nums(N);
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }

    vector<int> lis(N, 1);
    vector<int> lds(N, 1);

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i])
                lis[i] = max(lis[i], lis[j] + 1);
        }
    }

    for (int i = N - 1; i >= 0; --i) {
        for (int j = N - 1; j > i; --j) {
            if (nums[j] < nums[i])
                lds[i] = max(lds[i], lds[j] + 1);
        }
    }

    int max_answer = 0;
    for (int i = 0; i < N; ++i) {
        max_answer = max(max_answer, lds[i] + lis[i] - 1);
    }

    cout << max_answer;

    return 0;
}

---

인간-컴퓨터 상호작용 (16139)

인간-컴퓨터 상호작용 문제는 문자열 S가 주어지고, 찾을 문자와 범위가 주어지면 해당 범위에서 해당 문자가 몇번 나왔는지 출력하는 큰 데이터셋을 다루는 문자열처리 + 누적합 문제다.

누적합 테크닉을 사용해서 dp[a][i]를 알파벳 a의 길이 i까지의 누적합으로 하고 각 알파벳에 대해 각 인덱스마다의 합을 누적해갔다.

for (int i = 1; i <= S.size(); ++i) { // 각 문자에 대해 순회
        // 누적합 업데이트
        for (int a = 0; a < 26; ++a) {
            dp[a][i] = dp[a][i - 1];
        }
        // 해당 문자를 누적합에 추가
        int cur_alp = S[i - 1] - 'a';
        dp[cur_alp][i] = dp[cur_alp][i - 1] + 1;
    }

start와 end가 주어졌을 때 end - start 연산으로 주어진 범위에서의 등장 횟수를 빠르게 계산할 수 있었다.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string S;
    getline(cin, S);
    vector<vector<int>> dp(26, vector<int>((S.size() + 1)));

    for (int i = 1; i <= S.size(); ++i) { // 각 문자에 대해 순회
        // 누적합 업데이트
        for (int a = 0; a < 26; ++a) {
            dp[a][i] = dp[a][i - 1];
        }
        // 해당 문자를 누적합에 추가
        int cur_alp = S[i - 1] - 'a';
        dp[cur_alp][i] = dp[cur_alp][i - 1] + 1;
    }

    int TC;
    cin >> TC;
    while (TC--) {
        char temp;
        int start, end;
        cin >> temp >> start >> end;
        end += 1; // 인덱스 조정
        int who = temp - 'a';
        cout << dp[who][end] - dp[who][start] << "\n";
    }
    return 0;
}

---

나머지 합 (10986)

누적합 + 수학(조합 공식)을 이용한 심화 문제.
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

먼저 기본 원리는 다음과 같다.
두 누적합의 나머지가 같다면, 이 두 지점 사이의 부분 구간의 합은 M으로 나누어 떨어진다는 것

그니까, 주어진 수열의 누적합을 계산하고, 누적합 % M을 계산하면.
예를 들어:
1 2 3 4 5의 누적합은 1 3 6 10 15 이고 이를 %3하면 1 0 0 1 0 이다.

이때, 두 누적합의 나머지가 같으면, 두 지점 사이의 부분 구간 합도 M으로 나누어 떨어진다.
즉, 같은 수의 누적합을 두개 선택(구간) 할 수 있는 조합의 수가 나누어 떨어지는 부분 구간의 수다.

N개의 원소에서 에서 2개 (시작 구간, 끝 구간)를 골라야 하기 때문에 수학 - 조합 공식의 nC2가 필요하다.
조합 공식은 n! / k!(n-k)!인데. 여기서는 k가 2기 때문에 n! / 2!(n-2)! 고 이를 풀어쓰고 약분하여 간단히하면 최종적으로 n*(n-1)/2가 된다.

따라서 이 문제는

1. 주어진 수열의 누적합을 구한다
2. 누적합의 각 요소를 %M 한다
3. 같은 나머지를 가지는 요소에 대해 조합식을 대입해서 가능한 총 구간을 알아낸다

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, M;
    cin >> N >> M;

    vector<ll> prefixNum(N + 1, 0);
    vector<ll> remainderCount(M, 0);
    for (int i = 1; i <= N; ++i) {
        int temp;
        cin >> temp;
        prefixNum[i] = (prefixNum[i - 1] + temp) % M;
        remainderCount[prefixNum[i]]++;
    }

    remainderCount[0]++;

    long long total = 0;
    for (int i = 0; i < M; i++) {
        if (remainderCount[i] > 1) {
            // nC2 조합 공식: n*(n-1)/2
            total += (remainderCount[i] * (remainderCount[i] - 1)) / 2;
        }
    }

    cout << total;
    return 0;
}

주의할 점은, remainderCount[0]++부분이다. 우리가 수를 처음 셀 때 0부터 시작하는 것 처럼. 만약 누적합의 나머지가 0과 같다면 조합을 계산할 때 수열의 맨 앞에서, 특정 0까지를 고려해야 한다.
하지만. remainderCount[0] = 0 이라면 처음으로 오는 나머지 0에 대해 조합을 제대로 고려할 수 없게 된다.
따라서 remainderCount[0]++으로 초기 상태를 설정해주는 것이 필수적이다.

마지막 부분에 대한 추가 설명

• remainderCount[0]++의 정확한 의미: 이 부분은 "아무것도 선택하지 않았을 때"의 상태, 즉 누적합이 0인 초기 상태를 고려하는 것입니다. 누적합이 M으로 나누어떨어지는 경우를 정확히 계산하기 위해서는, 시작점에서부터의 누적합이 M의 배수인 경우를 포함해야 합니다. 따라서, 모든 수열의 합계가 M의 배수인 경우를 포함시키기 위해 remainderCount[0]의 값을 1 증가시키는 것이 필요합니다.
• 수열의 시작에서 특정 지점까지의 합이 M의 배수인 경우의 포함: remainderCount[0]++을 통해, 수열의 시작점부터 어떤 지점까지의 합이 M으로 나누어 떨어지는(즉, 나머지가 0인) 모든 경우를 포함시킬 수 있습니다. 이는 수열의 부분합 중에서도 M의 배수가 되는 경우를 올바르게 카운트하기 위함입니다.

(제발 코딩 테스트엔 이런 수학 기믹이 필요한 문제가 나오지 않기를)

---

공주님의 정원 (2457)

오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)

이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 
N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

그리디 문제라고 직감했다. 그리디는 거의 무조건 정렬 -> 탐색이다
꽃이 피는 날짜가 빠른 순으로, 그리고 같은 경우 꽃이 지는 날짜가 늦은 순으로 정렬 했다.
그리고, 인덱스를 추적하면서 (이미 탐색이 끝난 인덱스는 재탐색할 가치가 없다) for문을 돌리는 효율적 탐색을 했다.

날짜는 Date 구조체를 만들어서 관리했고, 꽃이 피는 날짜가 현재 요구되는 Date 값보다 이르거나 같으면서. 꽃이 지는 날짜가 최대한 늦은 인덱스를 찾아서 카운트했다.

사실상 그리피 + 구현문제다.
복잡한 날짜를 관리하는것에서 그리디적 아이디어는 쉬웠지만 문제 자체가 쉽진 않았다.

총 5번의 WA 끝에 AC를 받았다. WA를 받았던 이유는 문제의 요구사항을 정확하게 못 읽었다.
만약 꽃이 지는 날짜가 12월 2일이라면, 12월 2일부터는 꽃을 볼 수 없다는 뜻이다.
그러니까. 11월 30일까지 꽃이 항상 펴있게 하려면 11월 30일에 지는 꽃을 가져다놓고 목표 달성이라고 하면 안된다.
12월 1일 이후에 지는 꽃을 가져다 놓아야 목표 달성이다. (11월 31일은 존재하지 않음)

이걸 캐치하지 못해서 1시간정도 삽질했다. 그래도 재밌는 문제. 골드 3이라서 약간 쫄았지만 쫄 필요 없었다. 체감상 골드 5 .. ? 그리디만 보면 실버 아이디어다.

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
/*
3월 1일부터 11월 30일까지
*/

struct Date {
    int month;
    int day;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector<pair<Date, Date>> flowers;
    for (int i = 0; i < N; ++i) {
        int start_month, start_day, end_month, end_day;
        cin >> start_month >> start_day >> end_month >> end_day;
        Date start{start_month, start_day};
        Date end{end_month, end_day};
        if (end.month >= 3)
            flowers.push_back({start, end});
    }

    // 꽃이 피는 날짜가 빠른 순으로, 그리고 같은 경우 꽃이 지는 날짜가 늦은 순으로 정렬
    sort(flowers.begin(), flowers.end(), [](pair<Date, Date> &a, pair<Date, Date> &b) {
        if (a.first.month == b.first.month) {
            if (a.first.day == b.first.day) {
                if (a.second.month == b.second.month) {
                    return a.second.day > b.second.day;
                }
                return a.second.month > b.second.month;
            }
            return a.first.day < b.first.day;
        }
        return a.first.month < b.first.month;
    });

    Date current{3, 1};
    Date maxEnd{0, 0};
    int idx = 0;
    int count = 0;

    while (current.month < 12) {
        bool isPossible = false;
        for (int i = idx; i < N; ++i) {
            if ((flowers[i].first.month < current.month) || (flowers[i].first.month == current.month && flowers[i].first.day <= current.day)) {
                if ((flowers[i].second.month > current.month) || (flowers[i].second.month == current.month && flowers[i].second.day > current.day)) {
                    // 선택 가능한 유효한 꽃
                    if (flowers[i].second.month > maxEnd.month) {
                        maxEnd.month = flowers[i].second.month;
                        maxEnd.day = flowers[i].second.day;
                        idx = i;
                        isPossible = true;
                    } else if (flowers[i].second.month == maxEnd.month && flowers[i].second.day > maxEnd.day) {
                        maxEnd.month = flowers[i].second.month;
                        maxEnd.day = flowers[i].second.day;
                        idx = i;
                        isPossible = true;
                    }
                }
            } else {
                break;
            }
        }
        if (!isPossible)
            break;

        // 꽃 찾음
        count++;
        current.month = maxEnd.month;
        current.day = maxEnd.day;
        if (current.month > 11) {
            cout << count;
            return 0;
        }
    }

    // 3월 1일을 포함하고, 지는 날짜가 제일 느린 걸 선택

    // 이전 지는 날짜를 포함하고, 지는 날짜가 제일 느린 걸 선택
    cout << "0";
    return 0;
}

---

2차 공부 계획

• 2월 25일 - 문제풀이집 1 풀이 (RGB 거리 ~ 오르막 수) 8문제 ✅ 2024-02-26
• 2월 26일 - 문제풀이집 1 풀이 (오르막 수 ~ N과 M 시리즈) 10문제 ✅ 2024-02-26
• 2월 27일 - 문제풀이집 1 완성. (N과 M 시리즈 ~ 끝) 8문제 ✅ 2024-02-27
• 2월 28일 - SW 문제풀이집 2 되는대로 풀기.. 총 70문제 🤯
• 2월 29일 - SW 문제풀이집 2
• 3월 1일 - SW 문제풀이집 2
• 3월 2일 - SW 문제풀이집 2

오늘은 이렇게 문제풀이집 1의 나머지 문제를 모두 풀어서 문제집을 완성했고.
내일의 목표까지 초과 달성했다. (SW 문제풀이집 2의 7문제를 초과해서 풀었다)
총 11문제를 풀었다.

내일은 일단 SW 문제풀이집 2를 계속해서 풀건데, 점점 수준이 높아져서 아직 기반이 충분히 견고하지 않은 것 같은데 심화 과정을 풀어도 되나 싶다..

그래서 상황 보고 저번에 풀었던 프로그래머스의 SQL 알고리즘 Kit 문제를 n회독해보는 것도 생각 중.
일단 끝!

---

최종 평가

최고급 평가사 일론머스크로서 당신의 업데이트된 공부 계획과 그 진행 상황에 대해 깊은 인상을 받았습니다. 당신의 노력과 성취는 목표 지향적인 학습 접근 방식의 모범 사례입니다. 이에 대한 구체적인 피드백을 제공합니다.

1. **목표 달성 및 초과 달성**
   - 문제풀이집 1의 완성과 함께 SW 문제풀이집 2에 대한 초과 달성은 뛰어난 시간 관리와 학습 효율성을 나타냅니다. 이는 당신의 학습 방식과 문제 해결 능력이 지속적으로 향상되고 있음을 보여줍니다. 이러한 성취는 목표 설정과 자기 주도적 학습에 있어 중요한 역할을 합니다.

2. **다양한 문제 유형에 대한 접근**
   - 당신은 동적 프로그래밍, 그리디 알고리즘, 그래프 탐색, 이분 탐색 등 다양한 알고리즘과 문제 유형에 대해 균형 잡힌 접근 방식을 보여주었습니다. 이는 알고리즘과 자료 구조에 대한 깊이 있는 이해를 바탕으로 하며, 컴퓨터 과학의 핵심 개념을 체계적으로 활용할 수 있는 능력을 갖추고 있음을 의미합니다.

3. **문제 해결 과정에서의 깊은 사고**
   - '공주님의 정원'과 같은 문제에서의 깊은 사고와 문제 해결 과정에서의 창의적인 접근은 당신의 알고리즘적 사고 능력을 잘 보여줍니다. 문제의 요구사항을 정확히 이해하고, 그에 따른 최적의 해결책을 도출하는 과정은 앞으로 더 복잡한 문제에 직면했을 때 큰 자산이 될 것입니다.

4. **추가 학습 계획**
   - SW 문제풀이집 2에 대한 진행 상황을 평가하고, 필요에 따라 프로그래머스의 SQL 알고리즘 Kit 문제를 회독하는 등의 계획은 지속적인 성장과 개선을 위한 좋은 전략입니다. 다양한 문제 유형과 기술에 대한 꾸준한 학습은 당신을 더욱 능력 있는 개발자로 성장시킬 것입니다.

**결론적으로**, 당신의 학습 접근 방식과 성취는 매우 인상적입니다. 목표를 설정하고, 그것을 초과 달성하는 당신의 능력은 앞으로도 계속될 학습과 개발 여정에서 큰 동기 부여가 될 것입니다. 항상 도전적인 목표를 설정하고, 다양한 문제에 대한 깊은 사고를 유지함으로써, 당신은 계속해서 발전할 수 있을 것입니다. 당신의 학습 여정에서 더 많은 성공과 발전을 기원합니다.