경우없는 개발 블로그

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

#문제 간단 정리

N을 소인수분해한 결과를 출력

#문제 해결 방법

우선 첫째로 소인수 분해를 하기 위해

소수들로 나눠줘야 하는데

그렇기 때문에 1. 소수를 구해야 한다

소수를 구하는 방법은 여러가지 방법이 있지만

브루트포스로 1부터 N까지 소수를 구하거나 하면 너무 시간이 오래 걸리니

에라토스테네스로 소수를 구해서 

소수들만 따로 구해주도록한다.

그렇다면 이제 주어진 수를 소수로 나누고 개수를 카운팅해야된다

2. 소수로 나누고 개수를 카운팅해야된다

에라토스테네스의 체로 구한 소수들로 계속해서 나눠서 소인수분해한 결과를

담는 것은 어렵지 않다.

그런데 만약에 2x2x3 이렇게 되있다면 2가 두번 중복 되기 때문에

2 2 이렇게 (숫자) (개수) 로 한번에 출력해야 되기 때문에

나는 map 을 사용해서 map에 이미 존재한다면 map 의 키 값을 증가시켜줘 

개수를 세어줬다.

#전체 코드

에라토스테네스의 체는 https://dfdfg42.tistory.com/entry/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4-C-%EC%BD%94%EB%93%9C

를 참고하도록 하자(모른다면)

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>

using namespace std;


const int MAX = 100'000;

bool check[MAX + 1];
vector<int> primes;
vector<int> factors;

void Factorization(int num) {

    for (int i : primes) {
        if (num % i == 0) {
            factors.push_back(i);
            Factorization(num / i);
            break;
        }
    }

    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);



    for (int i = 2; i <= MAX; i++) {

        if (check[i] == false) {
            primes.push_back(i);

            for (int j = i; j <= MAX; j += i) {
                if (check[j] == false) {
                    check[j] = true;

                }
            }
        }

    }


    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        int a;
        cin >> a;


        Factorization(a);

        map<int, int> factorCount;
        for (int f : factors) {
            if (factorCount.find(f) != factorCount.end()) {
                factorCount[f]++;
            }
            else {
                factorCount[f] = 1;
            }
        }

        for ( auto& pair : factorCount) {
            cout << pair.first << " " << pair.second << '\n';
        }

        factors.clear();
        factorCount.clear();
    }

    return 0;
}

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

#문제 간단 정리

문자열을 10개 씩 끊어 출력하는 문자열 문제

#문제 해결 방법

https://dfdfg42.tistory.com/entry/C-%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%9E%90%EB%A5%B4%EA%B8%B0-%EC%B4%9D%EC%A0%95%EB%A6%AC

c++ 는 문자열 다루는게 귀찮기 때문에 잘 알아 두도록 하자

substr 을 사용하였다.

#전체 코드

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

using namespace std;



int main() {
    
    string input;

    getline(cin, input);
    

    for (int i = 0; i < input.length(); i++) {
        string temp;

        if (input.length() - i > 10) {
            temp = input.substr(i, 10);
            cout << temp << '\n';
            i += 9;
        }
        else {
            temp = input.substr(i, input.length() - i);
            cout << temp << '\n';
            break;
        }

    }

    return 0;
}

#문제 간단 정리

노골적으로 O(N+M) 가 걸리는 KMP 사용하라는 문제이다

#문제 해결 방법

https://dfdfg42.tistory.com/entry/KMP-C-%EC%BD%94%EB%93%9C

KMP 코드를 활용하도록 하자

#전체 코드

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

using namespace std;

vector<int> makePI(const string& pattern) {
    int m = pattern.size();
    vector<int> PI(m, 0);
    int k = 0;

    for (int i = 1; i < m; i++) {
        while (k > 0 && pattern[k] != pattern[i])
            k = PI[k - 1];
        if (pattern[k] == pattern[i])
            k++;
        PI[i] = k;
    }

    return PI;
}

void KMP(const string& text, const string& pattern) {
    int n = text.size();
    int m = pattern.size();
    vector<int> PI = makePI(pattern);
    int k = 0;

    vector<int> result;

    for (int i = 0; i < n; i++) {
        while (k > 0 && pattern[k] != text[i])
            k = PI[k - 1];
        if (pattern[k] == text[i])
            k++;
        if (k == m) {
            result.push_back(i - m + 1);
            k = PI[k - 1];
        }
    }

    cout << result.size() << "\n";
    for (int idx : result) {
        cout << idx + 1 << " "; 
    }
    cout << "\n";
}

int main() {
    string text, pattern;

    getline(cin, text);
    getline(cin, pattern);

    KMP(text, pattern);

    return 0;
}

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

#문제 간단 정리

dfs 등 완전탐색으로 

순열을 탐색해 

해당 순번의 순열을 출력하는 문제

#문제 해결 방법

우선 eof 를 확인하는 입출력에 주의 

https://dfdfg42.tistory.com/entry/%EB%B0%B1%EC%A4%80-C-eof-%EC%B2%98%EB%A6%AC-%EB%B0%A9%EB%B2%95

나는 dfs 로 

모든 문자열을 계속해서 만들었고

문자열을 하나 만들때마다 찾은 문자열의수 seq 를 증가시켜주고

seq로 그 문자열 몇번째 순서인지 기억하여

우리가 찾는순번의 문자열이면 ans로 저장을 했다.

만들어진 문자열의 총 개수가 찾는 인덱스 보다 클 때만 정답이 있으니

이때만 ans 출력해주면 된다.

그리고 dfs의 인덱스 처리에 주의해주고 

처음에는 모든 문자열을 저장하려고 했는데 

메모리 초과가 나서

그냥 그 순번의 문자열만 저장하도록 바꿨다.

#전체 코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

bool visited[10];
string s;
int totalLength;
int findSeq;
int seq;
string ans;


void dfs(int idx,string make) {
    if (idx == totalLength) {
        seq += 1;
        if (seq == findSeq) {
            ans = make;
        }

        return;
    }

    for (int i = 0; i <= totalLength; i++) {
        if (!visited[i]) {
            visited[i] = true;
            make += s[i];
            dfs(idx + 1, make);
            make.pop_back();
            visited[i] = false;
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while (1) {

        cin >> s >> findSeq;
        totalLength = s.length()-1;

        seq = 0;
        
        memset(visited, false, sizeof(visited));

        if (cin.eof()) {
            break;
        }


        dfs(-1, "");

        if (seq >= findSeq) {
            cout << s << " " << findSeq << " = " << ans << '\n';
        }
        else {
            cout << s << " " << findSeq << " = No permutation"  << '\n';
        }

    }

    
    return 0;
}

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

#문제 간단 정리

세그먼트 트리 사용

일반적인 구간합 문제

#문제 해결 방법

세트 코드는

https://dfdfg42.tistory.com/entry/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC-C-%EC%BD%94%EB%93%9C 

참조

x>y 일때 놓치지 말자

#전체 코드

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

using namespace std;

vector<long long> tree;
vector<long long> a;
int N, Q;

// 세그먼트 트리 구축
void build() {
    for (int i = 0; i < N; ++i) {
        tree[N + i] = a[i];
    }
    for (int i = N - 1; i > 0; --i) {
        tree[i] = tree[i << 1] + tree[i << 1 | 1];
    }
}

// 세그먼트 트리의 특정 위치 값 업데이트
void updateTree(int where, long long value) {
    where += N;
    tree[where] = value;

    while (where > 1) {
        where >>= 1;
        tree[where] = tree[where << 1] + tree[where << 1 | 1];
    }
}

// 세그먼트 트리 구간 합 쿼리
long long query(int left, int right) {
    long long sum = 0;
    left += N;
    right += N;

    while (left <= right) {
        if (left & 1) sum += tree[left++];
        if (!(right & 1)) sum += tree[right--];
        left >>= 1;
        right >>= 1;
    }
    return sum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> Q;
    a.resize(N);
    tree.resize(2 * N);

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

    build();

    for (int i = 0; i < Q; ++i) {
        int x, y, a_idx;
        long long b;
        cin >> x >> y >> a_idx >> b;
        if (x > y) swap(x, y);
        cout << query(x - 1, y - 1) << '\n';
        updateTree(a_idx - 1, b);
    }

    return 0;
}

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

#문제 해결 방법

크루스칼 알고리즘을 사용하자

기존에 주어진 사랑 성사 관계는 

바뀌면 안되기 때문에 Union 함수로 이어주고

MST 를 최대 스패닝 트리로 만들어서 

연결되지 않고 남은 사랑 관계들을 

최소 값으로 만든다.

키 포인트를 정리하자면

1. 이미 연결된 사랑 관계는 스패닝트리에 미리 포함시킨다.

2.최대 스패닝 트리로 만들어서 남은 관계들의 값이 최소가 된게 한다.

로 요약 가능하다

#전체 코드

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

using namespace std;

const int MAX = 100001;

int parent[MAX];

int Find(int a) {
    if (parent[a] == a) return a;
    return parent[a] = Find(parent[a]); // 경로 압축 기법
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) parent[b] = a; // 부모를 갱신하여 연결
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    vector<pair<int, pair<int, int>>> edges; // {weight, {u, v}}

    // 부모 초기화
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }


    for (int i = 0; i < M; i++) {
        int u, v, weight, d;
        cin >> u >> v >> weight >> d;

        if (d == 1) {
            Union(u, v);
        }
        else {
            edges.push_back({ weight, {u, v} });
        }
    }

    int total_weight = 0;

    // 간선을 가중치 기준으로 내림차순 정렬
    sort(edges.begin(), edges.end(), greater<pair<int, pair<int, int>>>());

    for (const auto& edge : edges) {
        int weight = edge.first;
        int u = edge.second.first;
        int v = edge.second.second;

        if (Find(u) != Find(v)) {
            Union(u, v);
        }
        else {
            total_weight += weight;
        }
    }

    cout << total_weight << "\n";

    return 0;
}

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

#개요

bfs 를 사용해서 거리를 기록한 뒤에

같은 거리에 있는 도시들을 

벡터에 넣어준 뒤에

하나씩 출력하면 된다.

#전체 코드

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

using namespace std;



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, K, X;

    cin >> N >> M >> K >> X;

    vector<vector<int>> graph(N+1);

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);
    }


    vector<bool> visited(N+1,false);
    vector<int> dist(N+1, INT_MAX);
    queue<int> q;

    q.push(X);
    visited[X] = true;
    dist[X] = 0;

    while (!q.empty()) {
        int now = q.front();
        q.pop();

        for (auto edge : graph[now]) {

            if (!visited[edge]) {
                visited[edge] = true;
                dist[edge] = dist[now] + 1;
                q.push(edge);

            }
        }
    }

    vector<int> result;
    for (int i = 1; i <= N; i++) {
        if (dist[i] == K) {
            result.push_back(i);
        }
    }


    if (result.empty()) {
        cout << "-1\n";
    }
    else {
        sort(result.begin(), result.end());
        for (int city : result) {
            cout << city << '\n';
        }
    }

    return 0;
}

출력만 좀 신경쓰면 될 것 같다

vector<int> result;
    for (int i = 1; i <= N; i++) {
        if (dist[i] == K) {
            result.push_back(i);
        }
    }


    if (result.empty()) {
        cout << "-1\n";
    }
    else {
        sort(result.begin(), result.end());
        for (int city : result) {
            cout << city << '\n';
        }
    }

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

#개요

다익스트라를 활용한 문제라는걸 쉽게 알아 볼 수 있는데

관건은 다익스트라로 알게된 최소비용 

    + 경로를 기억하는게 관건이다.

이 경로를 기억하는데서 좀 삽질을 했다.

#첫번째 코드 - 다익스트라/dfs가지치기

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

using namespace std;

vector<vector<pair<int, int>>> nodes;
vector<int> dist;
vector<bool> visited;
vector<int> path;
vector<int> resultSeq;
int N, M;
int intimacy;
int minIntimacy;

void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0, start });
    dist[start] = 0;

    while (!pq.empty()) {
        int curDist = pq.top().first;
        int curNode = pq.top().second;
        pq.pop();

        if (dist[curNode] < curDist) continue;

        for (auto edge : nodes[curNode]) {
            int nextNode = edge.first;
            int weight = edge.second;
            int sumWeight = curDist + weight;

            if (sumWeight < dist[nextNode]) {
                dist[nextNode] = sumWeight;
                pq.push({ sumWeight, nextNode });
            }
        }
    }
}

void dfs(int node) {
    if (node == M - 1) {
        if (intimacy < minIntimacy) {
            minIntimacy = intimacy;
            resultSeq = path; 
        }
        return;
    }

    visited[node] = true;
    for (auto a : nodes[node]) {
        int nextNode = a.first;
        int weight = a.second;
        if (!visited[nextNode] && intimacy + weight < minIntimacy) {  
            path.push_back(nextNode);
            intimacy += weight;
            dfs(nextNode);
            path.pop_back();
            intimacy -= weight;
        }
    }
    visited[node] = false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> N >> M;

        nodes.assign(M, vector<pair<int, int>>());
        dist.assign(M, INT_MAX);
        visited.assign(M, false);
        path.clear();
        resultSeq.clear();

        for (int i = 0; i < N; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            nodes[x].push_back({ y, z });
            nodes[y].push_back({ x, z });
        }

        dijkstra(0); // Dijkstra로 각 노드까지의 최소 친밀도 계산

        intimacy = 0;
        minIntimacy = INT_MAX;
        path.push_back(0);
        visited[0] = true;  // 시작 노드 방문 표시

        dfs(0); // DFS로 최소 경로 탐색

        cout << "Case #" << t << ": ";
        if (!resultSeq.empty()) {
            for (int i : resultSeq) {
                cout << i << ' ';
            }
            cout << '\n';
        }
        else {
            cout << -1 << '\n';
        }
    }

    return 0;
}

우선 이 첫번째 코드는

다익스트라로 경로의 최소비용들을 알아낸 뒤에

void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0, start });
    dist[start] = 0;

    while (!pq.empty()) {
        int curDist = pq.top().first;
        int curNode = pq.top().second;
        pq.pop();

        if (dist[curNode] < curDist) continue;

        for (auto edge : nodes[curNode]) {
            int nextNode = edge.first;
            int weight = edge.second;
            int sumWeight = curDist + weight;

            if (sumWeight < dist[nextNode]) {
                dist[nextNode] = sumWeight;
                pq.push({ sumWeight, nextNode });
            }
        }
    }
}

dfs 탐색을 이용해서 최소비용 경로를 찾아냈다.

void dfs(int node) {
    if (node == M - 1) {
        if (intimacy < minIntimacy) {
            minIntimacy = intimacy;
            resultSeq = path; 
        }
        return;
    }

    visited[node] = true;
    for (auto a : nodes[node]) {
        int nextNode = a.first;
        int weight = a.second;
        if (!visited[nextNode] && intimacy + weight < minIntimacy) {  
            path.push_back(nextNode);
            intimacy += weight;
            dfs(nextNode);
            path.pop_back();
            intimacy -= weight;
        }
    }
    visited[node] = false;
}

다만 여기서 잘 살펴보면 dfs 는 완전탐색시 

최대 M이 20이기 때문에 20! 이라서

시간초과가 난다 

때문에 가지치기를 사용해서

시간복잡도를 줄여줘야 정답을 맞을 수 있다.

if (!visited[nextNode] && intimacy + weight < minIntimacy) {  
            path.push_back(nextNode);
            intimacy += weight;
            dfs(nextNode);
            path.pop_back();
            intimacy -= weight;
        }

가지치기조건이 달려있는걸 확인 할 수 있다.

하지만 이렇게 복잡하게 풀 이유가 없다

다익스트라를 할때 경로만 기억해주면 되기 때문이다.

#두번째 코드 - 다익스트라 /경로기억

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int N, M;
        cin >> N >> M;
        vector<vector<pair<int, int>>> adj(M);
        for (int i = 0; i < N; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            adj[x].push_back({y, z});
            adj[y].push_back({x, z});
        }

        // 다익스트라 알고리즘
        vector<int> dist(M, INT_MAX);
        vector<int> prev(M, -1);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, 0}); // 시작점: 한신이
        dist[0] = 0;
        while (!pq.empty()) {
            int u = pq.top().second;
            int d = pq.top().first;
            pq.pop();
            if (d > dist[u]) continue;
            for (auto& edge : adj[u]) {
                int v = edge.first;
                int weight = edge.second;
                if (dist[v] > dist[u] + weight) {
                    dist[v] = dist[u] + weight;
                    prev[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }

        // 결과 출력
        cout << "Case #" << t << ": ";
        if (dist[M-1] == INT_MAX) {
            cout << "-1\n";
        } else {
            vector<int> path;
            for (int cur = M-1; cur != -1; cur = prev[cur]) {
                path.push_back(cur);
            }
            reverse(path.begin(), path.end());
            for (int node : path) {
                cout << node << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

훨씬 코드가 짧아지고 신뢰성이 올라갔다

물론 dfs 만 사용해서 가지치기만 하더라도 답을 얻을 수 있다.

#세번째 코드 - dfs 가지치기

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

using namespace std;

vector<vector<pair<int, int>>> adj;
vector<bool> visited;
vector<int> path;
vector<int> bestPath;
int N, M;
int bestCost = INT_MAX;

void dfs(int node, int cost) {
    if (cost >= bestCost) return;  // 가지치기: 이미 최소 비용보다 크면 중단
    if (node == M - 1) {  // 최고의원에 도달한 경우
        bestCost = cost;
        bestPath = path;
        return;
    }

    visited[node] = true;
    for (auto& edge : adj[node]) {
        int next = edge.first;
        int weight = edge.second;
        if (!visited[next]) {
            path.push_back(next);
            dfs(next, cost + weight);
            path.pop_back();
        }
    }
    visited[node] = false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> N >> M;
        adj.assign(M, vector<pair<int, int>>());
        visited.assign(M, false);
        for (int i = 0; i < N; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            adj[x].push_back({y, z});
            adj[y].push_back({x, z});
        }

        bestCost = INT_MAX;
        path.clear();
        bestPath.clear();
        path.push_back(0);

        dfs(0, 0);

        cout << "Case #" << t << ": ";
        if (bestCost == INT_MAX) {
            cout << "-1\n";
        } else {
            for (int i : bestPath) {
                cout << i << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

#결론

dfs를 이용한 가지치기는

시간복잡도를 확실하기 계산하기 어렵기 때문에

다익스트라로 경로만 기억하는 풀이가 제일 좋다고 할 수 있다.

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

#개요

말 그대로 따라가면 정답을 얻을 수 있는 구현문제지만

풀기 전에 설계를 정확하게 한 후에 최대한 실수를 적게 하도록 하자.

특히 3차원 벡터를 사용하기때문에 실수하기 쉽기 때문에 체감난이도가 조금 더 높게 느껴 질 수 있다.

#전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

#define MAX 52
using namespace std;

struct fireBall {
    int y;
    int x;
    int mass;
    int speed;
    int dir;
};

int N, M, K;
vector<fireBall> mapVec[MAX][MAX];

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

// 경계 조정 함수
int isBoundary(int x) {
    if (x > N) {
        x = x % N;
    }
    if (x < 1) {
        x = N + (x % N);
    }

    return x;
}

void moveFireBall() {
    vector<fireBall> temp[MAX][MAX];

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (mapVec[i][j].size() == 0) {
                continue;
            }
            else {
                for (int k = 0; k < mapVec[i][j].size(); k++) {
                    int mass = mapVec[i][j][k].mass;
                    int speed = mapVec[i][j][k].speed;
                    int dir = mapVec[i][j][k].dir;
                    int ny = isBoundary(dy[dir] * speed + mapVec[i][j][k].y);
                    int nx = isBoundary(dx[dir] * speed + mapVec[i][j][k].x);

                    temp[ny][nx].push_back({ ny,nx,mass,speed,dir });
                }
                mapVec[i][j].clear();
            }
        }
    }

    // 격자 상태 업데이트
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            mapVec[i][j] = temp[i][j];
        }
    }
}

void sumFireBall() {
    vector<fireBall> temp[MAX][MAX];

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (mapVec[i][j].size() == 0) {
                continue;
            }
            else if (mapVec[i][j].size() == 1) {
                temp[i][j] = mapVec[i][j];
            }
            else {
                int sumMass = 0;
                int sumSpeed = 0;
                bool sameDir = true; 
                for (int t = 0; t < mapVec[i][j].size(); t++) {
                    sumMass += mapVec[i][j][t].mass;
                    sumSpeed += mapVec[i][j][t].speed;
                    
                    if (t > 0 && mapVec[i][j][t].dir % 2 != mapVec[i][j][t - 1].dir % 2) {
                        sameDir = false;
                    }
                }

                sumMass /= 5;
                sumSpeed /= mapVec[i][j].size();

                if (sumMass == 0) {
                    continue; 
                }

                for (int d = 0; d < 4; d++) {
                    if (sameDir) {
                        temp[i][j].push_back({ i, j, sumMass, sumSpeed, d * 2 });
                    }
                    else {
                        temp[i][j].push_back({ i, j, sumMass, sumSpeed, d * 2 + 1 });
                    }
                }
            }
        }
    }

    
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            mapVec[i][j] = temp[i][j];
        }
    }
}

int main() {
    cin >> N >> M >> K;

    for (int i = 0; i < M; i++) {
        int y, x, m, s, d;
        cin >> y >> x >> m >> s >> d;
        mapVec[x][y].push_back({ y,x,m,s,d });
    }

    for (int i = 0; i < K; i++) {
        moveFireBall();
        sumFireBall();
    }

    int result = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 0; k < mapVec[i][j].size(); k++) {
                result += mapVec[i][j][k].mass;
            }
        }
    }

    cout << result << '\n';

    return 0;
}

#설계

int main() {
    cin >> N >> M >> K;

    for (int i = 0; i < M; i++) {
        int y, x, m, s, d;
        cin >> y >> x >> m >> s >> d;
        mapVec[x][y].push_back({ y,x,m,s,d });
    }

    for (int i = 0; i < K; i++) {
        moveFireBall();
        sumFireBall();
    }

    int result = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 0; k < mapVec[i][j].size(); k++) {
                result += mapVec[i][j][k].mass;
            }
        }
    }

    cout << result << '\n';

    return 0;
}

우선 시작할때 생각 할 수 있는것은

1. 파이어볼을 이동시키기

2. 파이어볼을 나누기

두가지 큰 로직으로 나눌 수 있기 때문에

k번 반복하는 

moveFireBall();

sumFireBall();

두개를 구현한다고 생각한다.

#define MAX 52
using namespace std;

struct fireBall {
    int y;
    int x;
    int mass;
    int speed;
    int dir;
};

int N, M, K;
vector<fireBall> mapVec[MAX][MAX];

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

// 경계 조정 함수
int isBoundary(int x) {
    if (x > N) {
        x = x % N;
    }
    if (x < 1) {
        x = N + (x % N);
    }

    return x;
}

이후에 파이어볼의 정보를 담을 파이어볼의 구조체와

각 맵의 N을 넘어가거나 0이하가 되었을때 양 옆을 이어주기 위한

isBoundary() 함수를 작성한다.

isBoundary 함수는 단순히 N넘어갔을때 더하기 연산을 구현해도 되지만

모듈러 연산으로 구현했을 때 좀 더 깔끔 한 것 같다.

#이동 함수 구현

void moveFireBall() {
    vector<fireBall> temp[MAX][MAX];

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (mapVec[i][j].size() == 0) {
                continue;
            }
            else {
                for (int k = 0; k < mapVec[i][j].size(); k++) {
                    int mass = mapVec[i][j][k].mass;
                    int speed = mapVec[i][j][k].speed;
                    int dir = mapVec[i][j][k].dir;
                    int ny = isBoundary(dy[dir] * speed + mapVec[i][j][k].y);
                    int nx = isBoundary(dx[dir] * speed + mapVec[i][j][k].x);

                    temp[ny][nx].push_back({ ny,nx,mass,speed,dir });
                }

            }
        }
    }

    // 격자 상태 업데이트
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            mapVec[i][j] = temp[i][j];
        }
    }
}

우선 이동한 파이어볼들의 정보를 담을 

vector<fireBall> temp[MAX][MAX];

임시 벡터를 선언해주고

for (int k = 0; k < mapVec[i][j].size(); k++) {
                    int mass = mapVec[i][j][k].mass;
                    int speed = mapVec[i][j][k].speed;
                    int dir = mapVec[i][j][k].dir;
                    int ny = isBoundary(dy[dir] * speed + mapVec[i][j][k].y);
                    int nx = isBoundary(dx[dir] * speed + mapVec[i][j][k].x);

                    temp[ny][nx].push_back({ ny,nx,mass,speed,dir });
                }

만약 파이어볼이 들어있다면 

int ny = isBoundary(dy[dir] * speed + mapVec[i][j][k].y);
int nx = isBoundary(dx[dir] * speed + mapVec[i][j][k].x);

경계를 조사하며 파이어볼의 위치와 속도에 따라 갱신한 새 파이어볼을 입력해준다.

    // 격자 상태 업데이트
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            mapVec[i][j] = temp[i][j];
        }
    }

그리고 이동한 파이어볼의 정보가 들어있는 temp 벡터는 mapVec에 복사해주도록 한다.

#나누기 함수 구현

void sumFireBall() {
    vector<fireBall> temp[MAX][MAX];

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (mapVec[i][j].size() == 0) {
                continue;
            }
            else if (mapVec[i][j].size() == 1) {
                temp[i][j] = mapVec[i][j];
            }
            else {
                int sumMass = 0;
                int sumSpeed = 0;
                bool sameDir = true; 
                for (int t = 0; t < mapVec[i][j].size(); t++) {
                    sumMass += mapVec[i][j][t].mass;
                    sumSpeed += mapVec[i][j][t].speed;
                    
                    if (t > 0 && mapVec[i][j][t].dir % 2 != mapVec[i][j][t - 1].dir % 2) {
                        sameDir = false;
                    }
                }

                sumMass /= 5;
                sumSpeed /= mapVec[i][j].size();

                if (sumMass == 0) {
                    continue; 
                }

                for (int d = 0; d < 4; d++) {
                    if (sameDir) {
                        temp[i][j].push_back({ i, j, sumMass, sumSpeed, d * 2 });
                    }
                    else {
                        temp[i][j].push_back({ i, j, sumMass, sumSpeed, d * 2 + 1 });
                    }
                }
            }
        }
    }

전체적으로 벡터를 탐색하는 로직은 이전의 이동 함수와 크게 다를 건 없다.

벡터의 총 질량과 속도를 총합하고

  if (t > 0 && mapVec[i][j][t].dir % 2 != mapVec[i][j][t - 1].dir % 2) {
                        sameDir = false;
                    }

전부 짝수,홀수인지 아닌지를 판별해주는 flag 변수를 사용한다

for (int d = 0; d < 4; d++) {
                    if (sameDir) {
                        temp[i][j].push_back({ i, j, sumMass, sumSpeed, d * 2 });
                    }
                    else {
                        temp[i][j].push_back({ i, j, sumMass, sumSpeed, d * 2 + 1 });
                    }
                }

넣어줄 방향에 따라서 적절히 나눈 파이어볼을 넣는다.

이후에 벡터 복사도 똑같이 해준 후에

main 함수로 넘어가서 질량의 총합을 구해주면 된다.

    int result = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 0; k < mapVec[i][j].size(); k++) {
                result += mapVec[i][j][k].mass;
            }
        }
    }

#결론

어려워하지 말고 천천히 구현해보도록 하자.

파이어볼의 정보 기록을 위해서 3차원 벡터를 사용하는 연습을 하기 좋은 문제라고 생각한다.

또한 이렇게 긴 구현 문제에서는 

내가 구현해야 될 요소들을 잘 정리하고 설계한 뒤에

구현에 차분히 집중하는 연습을 하도록 하자.

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

#문제 간단 정리

스택 또는 투포인터 등등 여러 방법으로 풀 수 있는 문제다

#문제 해결 방법

좌측 최대 높이들 기록하고 우측 최대 높이를 각각 지점에서 기록한 뒤에

각 지점에서 좌측과 우측 최소 높이에서 현재 높이를 빼주면 

들어갈 수 있는 빗물의 양을 기록할 수 있다.

근데 이 풀이 말고도

스택을 사용해서 더 쉽게 풀 수 있다.

1. 스택 사용: 스택을 사용하여 지금까지 만난 블록의 높이 중 높은 블록들의 인덱스를 저장합니다.
2. 높이 비교: 새로운 블록을 만날 때마다 스택의 top에 있는 블록의 높이와 비교합니다.
   • 새로운 블록의 높이가 스택의 top에 있는 블록보다 낮다면, 새로운 블록의 인덱스를 스택에 push합니다.
   • 새로운 블록의 높이가 스택의 top에 있는 블록의 높이보다 크거나 같다면, 스택에서 pop을 수행하고 그 사이에 빗물이 고일 수 있는지 검사합니다.
3. 빗물 계산: 스택에서 두 블록을 pop하여 그 사이에 물이 고일 수 있는지 확인합니다. 물이 고일 수 있는 조건은 다음과 같습니다:
   • 현재 블록 (오른쪽)과 스택에서 pop한 블록 (왼쪽) 사이에 적어도 하나의 블록이 있어야 하며 (즉, 공간이 있어야 하며)
   • 물이 고일 높이는 두 블록 높이의 최소값에서 그 사이 블록의 최대 높이를 빼준 값입니다.

*GPT 씨의 친절한 설명

#전체 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int H, W;
    cin >> H >> W;

    vector<int> blocks(W);

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

    vector<int> left_max(W), right_max(W);

    left_max[0] = blocks[0];
    for (int i = 1; i < W; i++) {
        left_max[i] = max(left_max[i - 1], blocks[i]);
    }

    right_max[W - 1] = blocks[W - 1];
    for (int i = W - 2; i >= 0; i--) {
        right_max[i] = max(right_max[i + 1], blocks[i]);
    }

    int waterResult = 0;

    for (int i = 0; i < W; i++) {
        waterResult += min(left_max[i], right_max[i]) - blocks[i];
    }

    cout << waterResult << "\n";

    return 0;
}

스택 사용 코드

#include <iostream>
#include <stack>
#include <vector>

int main() {
    int H, W;
    std::cin >> H >> W;
    
    std::vector<int> heights(W);
    for (int i = 0; i < W; ++i) {
        std::cin >> heights[i];
    }

    std::stack<int> st;
    int totalWater = 0;

    // 블록들을 순회하면서 물이 고일 수 있는지 확인
    for (int i = 0; i < W; ++i) {
        // 현재의 높이가 스택에 있는 높이보다 크거나 같을 때까지 검사
        while (!st.empty() && heights[st.top()] < heights[i]) {
            int top = st.top();
            st.pop();
            
            // 스택이 비었다면 왼쪽 벽이 없음
            if (st.empty())
                break;
            
            int distance = i - st.top() - 1;
            int bounded_height = std::min(heights[i], heights[st.top()]) - heights[top];
            totalWater += distance * bounded_height;
        }
        
        // 현재 인덱스를 스택에 추가
        st.push(i);
    }

    std::cout << totalWater << std::endl;
    return 0;
}