코딩하는 두꺼비

programmers.co.kr/learn/courses/30/lessons/12913

처음 문제를 접했을때 DP로 푸는 것임을 직감할 수 있었다.

좀 더 깔끔하게 문제를 풀고 싶었는데 좋은 방법이 생각이 안나서 그냥 무작정 모든 경우의 수를 나눠서 풀었다.

DP배열 크기를 실수로 40004로 하니 segmentaion fault가 났던 것을 생각하면 항상 배열이나 벡터를 선언할때

사이즈를 잘보고 넉넉하게 선언하는 것이 중요할 것 같다.

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

int cmp(int a, int b, int c){
    int temp;
    temp = max(a,b);
    temp = max(temp, c);
    return temp;
}

int dp[400000];

int solution(vector<vector<int>> land){
    int answer = 0;
    int a = 0;
    for(int i = 0; i < land.size(); i++){
        for(int j = 0; j < 4; j++){
            dp[a] = land[i][j];
            a++;
        }
    }
    int n = land.size()*4;
    for(int i = 4; i < n; i++){
        if(i % 4 == 0){
            dp[i] += cmp(dp[i-1], dp[i-2], dp[i-3]);
        }else if(i % 4 == 1){
            dp[i] += cmp(dp[i-2], dp[i-3], dp[i-5]);
        }else if(i % 4 == 2){
            dp[i] += cmp(dp[i-3], dp[i-5], dp[i-6]);
        }else{
            dp[i] += cmp(dp[i-5], dp[i-6], dp[i-7]);
        }
    }
    answer = cmp(dp[n-1],dp[n-2],dp[n-3]);
    answer = max(answer, dp[n-4]);
    return answer;
}

www.acmicpc.net/problem/1922

앞서 풀었던 최소 스패닝 트리 문제와 사실상 동일한 문제였다.

하지만 런타임에러로 고생을 했었는데

edge.resize(100001);

이부분에서 resize를 m+1로 하니 너무 작게 선언한 것이 문제가 되어 결국 런타임에러가 발생해서 이유를 찾는데 고생을 했다.

다음 부터 mst문제를 풀 때에는 STL의 크기에 대해서 잘 생각을 하고 구현을 해야겠다고 생각했다.

또한 프림 알고리즘을 푸는 것이외에 크루스칼 알고리즘으로 푸는 것에 대해서도 공부를 좀 해봐야겠다.

#define _CRT_SECRUE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int n, m, sum;
int visit[10001];
vector<vector<pair<int, int>>> edge;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void prim(int v) {
	visit[v] = 1;
	for (auto u : edge[v]) {
		if (!visit[u.second]) {
			pq.push(u);
		}
	}

	while (!pq.empty()) {
		auto w = pq.top();
		pq.pop();
		if (!visit[w.second]) {
			sum += w.first;
			prim(w.second);
			return;
		}
	}
}

int main() {
	int a, b, c;
	cin >> n >> m;
	edge.resize(100001);
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		edge[a].push_back({ c,b });
		edge[b].push_back({ c,a });
	}
	prim(1);
	cout << sum;
	return 0;
}

www.acmicpc.net/problem/1197

문제를 보고 크루스칼 알고리즘이나 프림알고리즘으로 풀어야 겠다는 생각을 했는데

둘 다 실제로 구현해본적이 없어서 고민을 하다가

결국 답을 보고 풀 수 있었다..

#define _CRT_SECRUE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int v, e, c;
long long sum;
int visit[10001];
vector<vector<pair<int, int>>> edge;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void prim(int v) {
	visit[v] = 1;		//방문 노드 체크
	for (auto u : edge[v]) {
		if (!visit[u.second]) {		//방문 노드에 연결된 모든 간선 추가
			pq.push({ u.first, u.second });
		}
	}

	while (!pq.empty()) {		//방문 노드와 연결된 간선 중 최소값 더하기
		auto w = pq.top();
		pq.pop();
		if (!visit[w.second]) {
			sum += w.first;
			prim(w.second);
			return;
		}
	}
}

int main() {
	int x, y, z;
	cin >> v >> e;
	edge.resize(v + 1);
	for (int i = 0; i < e; i++) {
		cin >> x >> y >> z;
		edge[x].push_back({ z,y });
		edge[y].push_back({ z,x });
	}
	prim(1);
	cout << sum;
	return 0;
}

출처: dhpark-ghost.herokuapp.com/2018/06/12/c-peurim-prim-algorijeum/