코딩하는 두꺼비

www.acmicpc.net/problem/1107

이 문제는 나한테는 너무 악질같은 문제였다.

반례도 많은 데다가 런타임 에러까지 발생하니 너무 시간이 오래걸렸다.

또한 생각치도 못한 반례가 있어서 결국 못풀다가 답을 보고 풀 수 있었다ㅠㅠ

그냥 N*2의 모든 숫자들을 검색해서 최솟값을 찾는 것이 중요한 문제였는데 난 문자열로 바꾸어서 하나씩 비교해가며 찾는 잘못된 방식을 택하고 있었다.

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

bool broken[10];

int check(int c) {
	if (c == 0) {
		if (broken[0]) {
			return 0;
		}
		else {
			return 1;
		}
	}
	int len = 0;
	while (c > 0) {
		if (broken[c % 10]) {
			return 0;
		}
		c = c / 10;
		len += 1;
	}
	return len;
}

int main() {
	int n, m, x;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x;
		broken[x] = true;
	}
	int result = abs(n - 100);
	for (int i = 0; i <= 1000000; i++) {
		int c = i;
		int len = check(c);
		if (len > 0) {
			int press = abs(c - n);
			if (result > press + len) {
				result = press + len;
			}
		}
	}
	cout << result;
	return 0;
}

참고 블로그: seol-limit.tistory.com/48

www.acmicpc.net/problem/2470

처음에 이분 탐색이라 생각하고 풀었는데 기본적인 이분탐색 구조와 살짝 다르게 구현해야해서 시간이 좀 걸린 문제이다.

반례를 보고 풀 수 있었는데 left = right인 경우에 같은 값이 출력되는 것을 생각 못하게 구현한 것이 패인이였다.

결국 기본적인 이분탐색과 다르게 left <= right형식과 mid를 사용하지 않아서 약간 변형된 문제였다.

또한 두 개의 용액만을 더해야 하기 때문에 투 포인터로 좀 애매할 것 같아 투 포인터를 사용하지 않았다.

1. 이분 탐색을 위해 벡터를 정렬한다.

2. 0과 가까운 것을 알기 위해 조건을 절댓값으로 비교해준다.

3. 합이 0보다 작으면 left증가 0보다 크면 right를 증가해서 값을 비교해주었다.

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

vector<int> v;

int main() {
	int n, x;
	long long ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());

	int left = 0;
	int right = v.size() - 1;
	ans = v[left] + v[right];
	int ans1 = left;
	int ans2 = right;
	while (left < right) {
		long long sum = v[left] + v[right];
		if (abs(ans) > abs(sum)) {
			ans = sum;
			ans1 = left;
			ans2 = right;
		}
		if (sum > 0) {
			right -= 1;
		}
		else {
			left += 1;
		}

	}
	cout << v[ans1] << " " << v[ans2];
	return 0;
}

www.acmicpc.net/problem/1477

이분 탐색 문제를 몇개 풀어본 지라 나름 자신있게 도전을 했었다.

근데 우선 순위 큐를 사용해서 풀 수도 있을 것 같아 계속 하다보니 도저히 답을 구할 수 없었다.

그래서 결국 이분 탐색으로 풀려하는데 풀이법이 생각이 안나 다른 사람의 풀이를 결국 참고했다ㅠㅠ

예전에 풀었던 입국심사 문제와 조금 비슷한 면이 있는 문제 였는데 너무 생각없이 문제를 접근했던 것 같다.

다음 부턴 문제를 풀고 나서 확실히 이해하고 기억하는 습관을 길러야겠다

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

vector<int> v;

int main() {
	int n, m, l, x;
	cin >> n >> m >> l;
	v.push_back(0);
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	v.push_back(l);
	
	int left = 1;
	int right = l - 1;
	int mid = 0;
	while (left <= right) {
		mid = (left + right) / 2;
		int store = 0;
		for (int i = 1; i < v.size(); i++) {
			int d = v[i] - v[i - 1];
			store += d / mid;
			if (d % mid == 0) {
				store--;
			}
		}
		if (store > m) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	cout << left;
	return 0;
}

참고한 블로그: paris-in-the-rain.tistory.com/44

딱 깔끔하게 푸셔서 도움이 많이 되었다..

www.acmicpc.net/problem/1520

처음엔 그냥 DFS로 풀려고 했지만 계속 시간 초과가 나와서 고민을 많이 했다. 그냥 DFS를 사용하면 4^(500*500)번의 연산 횟수가 나온다는 것을 잘 몰랐다..

결국 풀다가 도저히 안되서 답을 보고 풀 수 있었는데 DP를 bottom up형식으로 써야하는 것이 어려웠던 문제이다.

문제 해설 중에는 이 블로그가 이해를 하는데 많이 도움을 준 것 같다.

wootool.tistory.com/83

결국 내가 푼 코드는

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

int map[501][501];
int dp[501][501];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int m, n;

int dfs(int x, int y) {
	if (!x && !y) {
		return 1;
	}
	if (dp[x][y] == -1) {
		dp[x][y] = 0;
		for (int i = 0; i < 4; i++) {
			int a = x + dx[i];
			int b = y + dy[i];
			if (a >= 0 && b >= 0 && a < m && b < n &&
				map[a][b] > map[x][y]) {
				dp[x][y] += dfs(a, b);
			}
		}
	}
	return dp[x][y];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			dp[i][j] = -1;
		}
	}
	cout << dfs(m-1, n-1);
	return 0;
}

DP를 이런식으로 사용할 수 도 있다는 것을 알 수 있었고 아직 부족함을 많이 느끼게 해준 문제였다.. ㅠㅠ

www.acmicpc.net/problem/1715

우선순위 큐 분류에 들어가 있는 골드4 난이도의 문제였다.

이 문제 같은 경우엔 두 묶음을 골라 합치면 비교 횟수가 줄어 드는 것을 생각하고 풀면 쉽게 풀리는 문제였다.

최소 우선 순위 큐에 각 카드 묶음들을 넣어주고 계속 2개씩 꺼내어 더한 후 다시 넣어주는 식으로 구현하였다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;

int main() {
	int n, x, ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		pq.push(x);
	}
	while (pq.size() > 1) {
		int a = pq.top();
		pq.pop();
		int b = pq.top();
		pq.pop();
		ans += a + b;
		pq.push(a + b);
	}
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/2075

힙 혹은 우선순위 큐에 대해서 공부를 하기 위해서 문제를 찾던 도중 발견한 문제이다.

그냥 기본적인 우선순위 큐를 사용해서 푸는 문제인데 메모리 제한이 있어서 이부분을 생각해

pop()을 넣어주는 것이 중요한 문제였다.

또한 시간 초과를 겪었는데 이 부분은 cin, cout을 사용할 경우

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

위와 같은 코드를 삽입해주어야 하고 아니면 그냥 scanf, printf를 사용해야 시간 초과가 나지 않는다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;

int main() {
	int n, x;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &x);
			pq.push(x);
			if (pq.size() > n) {
				pq.pop();
			}
		}
	}
	printf("%d", pq.top());
	return 0;
}

왜 난이도가 골드 4인지 약간 이해가 안되는 문제였다.. 아마 우선 순위 큐를 사용하지 않고 직접 구현하는 경우를 생각해서 그런 것 같다.

programmers.co.kr/learn/courses/30/lessons/68645#

쉬운 문제인 줄 알고 접근했는데 생각보다 어려워서 시간을 많이 썻다..

처음 접근할 때 3가지 방향을 나눠서 하는 법은 생각했지만 좌표를 설정해서 조절하는 것을 생각하지 못한 것이 잘못했다고 생각한다.

그래서 풀이를 위해서

1. 위에서 왼쪽 아래로 나가는 방향, 일직선 가로로 나가는 방향, 아래 오른쪽에서 위쪽 대각선으로 나가는 방향으로 모드를 나누었다. (이 부분은 모듈러 연산을 사용하는 것이 더깔끔할듯?)

2. x,y 좌표를 만들어서 n, n-1, n-2...씩 연산을 해주고 각 모드의 연산이 끝나면 x,y좌표를 재설정해주었다.

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

using namespace std;

int dal[1001][1001];

vector<int> solution(int n) {
    vector<int> answer;
    int mode = 1;
    int cnt = 1;
    int x = 0, y = 0;
    for(int i = n; i >= 1; i--){
        if(mode == 1){
            for(int j = 0; j < i; j++){
                dal[x+j][y] = cnt;
                cnt++;
            }
            x += i-1;
            y += 1;
            mode++;
        }else if(mode == 2){
            for(int j = 0; j < i; j++){
                dal[x][y+j] = cnt;
                cnt++;
            }
            x -= 1;
            y += i-2;
            mode++;
        }else{
            for(int j = 0; j < i ; j++){
                dal[x-j][y-j] = cnt;
                cnt++;
            }
            x -= i-2;
            y -= i-1;
            mode = 1;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < i; j++){
            answer.push_back(dal[i-1][j]);
        }
    }
    return answer;
}

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/