대엉코딩

www.acmicpc.net/problem/16235

1. 풀이방법

- 단순한 구현 문제입니다.

- 문제는 간단하고 이해도 어렵지 않지만, 시간제한이 0.3초 인 점을 감안하여야 합니다.

- 문제에서의 단계대로 차례차례 진행해줍니다.

2. 주의사항

- 전 처음에 시간제한 및 어린나이부터 진행되어야 한다는 문제를 보고 우선순위 큐를 생각해서 접근하였는데,

- 정답은 잘 뽑아내는 것 같으나, 시간초과가 계속 되어 결국 자료형을 vector로 바꿔서 봄에만 정렬을 하여 사용하였습니다.

- vector를 사용하자니, 죽은 나무를 뽑아내는 것이 문제였는데, vector는 index로 쉽게 접근이 가능하나 원하는 위치의데이터를 맘대로 뽑기는 어렵습니다.

- 그래서 양분이 부족해지는 지점이 딱 왔을 때, 그 이차원벡터배열의 맨뒤부터 양분/2를 더해주면서 pop_back() 해주었습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int n, m, K;
int ground[11][11]; // 양분의 양
vector<int> treeageset[11][11]; //나이 기준 정렬
int s2d2[11][11];
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
int tmpv[1001];
int presize[11][11]; 

void inputs() {
	cin >> n >> m >> K;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ground[i][j] = 5;
			cin >> s2d2[i][j];
		}
	}
	int x, y, z;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		treeageset[x][y].push_back(z);
	}
}
bool boundcheck(int x, int y) {
	return (x >= 1 && x <= n && y >= 1 && y <= n);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	for (int i = 0; i < K; i++) { //1년

		//봄
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (treeageset[j][k].empty()) continue;
				int tmpground = ground[j][k];
				ground[j][k] = 0;
				sort(treeageset[j][k].begin(), treeageset[j][k].end());
				int vsize = treeageset[j][k].size();
				for (int a = 0; a < vsize; a++) {
					if (tmpground >= treeageset[j][k][a]) {
						tmpground -= treeageset[j][k][a];
						treeageset[j][k][a]++;
					}
					else {
						for (int b = vsize - 1; b >= a; b--) {
							ground[j][k] += treeageset[j][k][b] / 2;
							treeageset[j][k].pop_back();
						}
						break;
					}
				}
				ground[j][k] += tmpground; //남은 양분+죽은나무의 양분
			}
		}


	//새로 추가되는 나무들은 번식시키지 않기 위해서
	for (int j = 1; j <= n; j++) { 
		for (int k = 1; k <= n; k++) {
			presize[j][k] = treeageset[j][k].size();
		}
	}
	//가을 번식
	for (int j = 1; j <= n; j++) {
		for (int k = 1; k <= n; k++) {
			for (int a = 0; a < presize[j][k]; a++) {
				if (treeageset[j][k][a] % 5 == 0) {
					for (int b = 0; b < 8; b++) {
						int nextx = j + dx[b];
						int nexty = k + dy[b];
						if (boundcheck(nextx, nexty)) {
							treeageset[nextx][nexty].push_back(1);
						}
					}
				}
			}
			ground[j][k] += s2d2[j][k]; //양분 보급
		}
	}
}
	int resultsum = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			resultsum += treeageset[i][j].size();
		}
	}
	cout << resultsum;
	return 0;
}

www.acmicpc.net/problem/1655

1. 풀이방법

 - 직관적인 풀이 : 중간값을 의미를 떠올리면 수빈이가 숫자를 하나 외칠 때 마다 정렬을 수행 후 중간에 위치한

                        값을 뽑아내면 된다 . ---> 시간초과 (아마? 작성해서 제출해보진 않았습니다.)

 - 우선순위 큐를 이용했습니다.

   (1단계)

      -가장 큰 값을 뽑아내는 pqless와 가장 작은 값을 뽑아내는 pqgreater를 선언 후 

      - 매 단계 마다, 그 전의 중간값을 기준으로 pqless에 넣을지 pqgreater에 넣을지를 판단해서 우선순위 큐에 삽입

   (2단계)

      - 중간값을 뽑아내기 위해서는 한쪽 우선순위 큐만 너무 커져 버리면 안됩니다 즉 데이터의 수가 1차이 이하로 나야

         하므로 2이상 차이가 날경우 큰 쪽의 우선순위 큐의 값을 작은 크기의 우선순위 큐 로 옮겨주는 작업을 수행

   (3단계)

      - 중간값을 뽑아내서 출력 (다음단계를 위한 중간값 저장)

      - 문제 조건에 따라서 두 우선순위큐의 사이즈를 비교한후 (편의상) 왼쪽 위에 뽑아낼지 오른쪽 위에서 뽑아낼지

         결정하면 됩니다.

2. 주의사항

 - 개인적으로는 우선순위 큐 두개를 사용해야 겠다 라는 생각이 든 이후 부터는 상대적으로 매우 쉬웠습니다.

 - 문제 조건에 따른 단계별 구현만 차근차근 해주시면 되겠습니다.

3. 나의코드

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

int N;
int centervalue;

priority_queue<int, vector<int>> pqless;
priority_queue<int, vector<int>, greater<int>> pqgreater;

void InputToQueue(int num) {
	if (num <= centervalue) { pqless.push(num); }
	else { pqgreater.push(num); }
}
void ModifyQueue() {
	if (pqless.size() > pqgreater.size() + 1) { //2이상 차이날 경우
		int modinum = pqless.top();
		pqless.pop();
		pqgreater.push(modinum);
	}
	else if (pqgreater.size() > pqless.size() + 1) { //2이상 차이날 경우
		int modinum = pqgreater.top();
		pqgreater.pop();
		pqless.push(modinum);
	}
}
void GetCenterValue() {
	if (pqless.size() >= pqgreater.size()) {
		centervalue = pqless.top();
	}
	else {
		centervalue = pqgreater.top();
	}
	cout << centervalue << "\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int tmp;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		if (i == 0) {
			pqless.push(tmp); centervalue = tmp; cout << centervalue << "\n"; continue;
		}
		InputToQueue(tmp);
		ModifyQueue();
		GetCenterValue();
	}
	return 0;
}

www.acmicpc.net/problem/1715

1. 풀이방법

- 작은 순서대로 정렬하여 카드 묶음을 묶어나가면 된다.

- 주의할 점은 처음에만 정렬하고 앞쪽부터 연산 한다고 해결되는 것이 아니다

- 만약에 20 30 40 45 70 이 있을 떄 20+30=50이 되고 연산 순서를 그대로 하면 50 40 45 70 이 된다.

- 이러면 50+40이 먼저 계산 되므로 분명 오답을 가지고 올 것이다.

- 그럼으로 한번의 연산을 할 때마다 계산을 앞으로 해야할 배열들은 정렬되어 있어야 한다.

2. 주의사항

- 위의 로직을 처음에 그대로 vector와 sort로 구현하였다...물론 답은 맞겠지만 입력사이즈를 고려하면 시간초과가 뜬다.

  (매 단계마다 sort를 할 경우)

- 그래서 priority_queue 우선순위 큐를 이용하였다 <오름차순으로> 그러면 단계마다 합친 결과를 push 할 때 정렬 되

- 어 큐에 들어가므로 sort를 할 필요가 없다.

- 한번에 두개를 큐에서 꺼내고 그 합을 다시 넣어주므로 반복문은 N번이 아닌 N-1번만 돈다.

3. 나의코드

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

int N;
priority_queue<int, vector<int>, greater<int>> carddeck;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int card;
	for (int i = 0; i < N; i++) {
		cin >> card; carddeck.push(card);
	}
	int minsum = 0;
	int tmpcard1, tmpcard2;
	for (int i = 0; i < N-1; i++) {
		tmpcard1=carddeck.top();
		carddeck.pop();
		tmpcard2 = carddeck.top();
		carddeck.pop();
		minsum += (tmpcard1 + tmpcard2);
		tmpcard2 += tmpcard1;
		carddeck.push(tmpcard2);
	}
	cout << minsum;
	return 0;
}