대엉코딩

www.acmicpc.net/problem/14499

1. 풀이방법

- 문제의 조건을 잘 파악합니다 (처음 읽으면 이게 뭔말인가......싶습니다.)

- 주사위에서 잠깐 멈칫했지만 주사위 전개도를 가지고 동/서/북/남 으로 돌렸을 때의 전개도도 그려보고

- 이동방향에 따라 값을 수정해주면 됩니다

- 저같은 경우 윗면은 항상 dice[1], 아랫면은 항상 dice[6]

2. 주의사항

- 문제를 읽고 이해하기

3. 나의코드

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


int N, M, K;
int x, y;
int jido[21][21];
int dice[7]; //주사위 (1~6면) //윗면이 무조건 dice[1] ,아랫면이 dice[6]
int dx[5] = { 0,0,0,-1,1 };
int dy[5] = { 0,1,-1,0,0 };

void movedice(int c) {
	if(c==1){ //동
		int tmpdice[7];
		tmpdice[6] = dice[3]; tmpdice[3] = dice[1];
		tmpdice[4] = dice[6]; tmpdice[1] = dice[4];
		tmpdice[5] = dice[5]; tmpdice[2] = dice[2];
		for (int i = 1; i < 7; i++) dice[i] = tmpdice[i];
	}
	if(c==2){
		int tmpdice[7];
		tmpdice[6] = dice[4]; tmpdice[3] = dice[6];
		tmpdice[4] = dice[1]; tmpdice[1] = dice[3];
		tmpdice[5] = dice[5]; tmpdice[2] = dice[2];
		for (int i = 1; i < 7; i++) dice[i] = tmpdice[i];
	}
	if (c == 3){
		int tmpdice[7];
		tmpdice[6] = dice[2]; tmpdice[2] = dice[1];
		tmpdice[5] = dice[6]; tmpdice[1] = dice[5];
		tmpdice[3] = dice[3]; tmpdice[4] = dice[4];
		for (int i = 1; i < 7; i++) dice[i] = tmpdice[i];
	}
	if (c == 4) {
		int tmpdice[7];
		tmpdice[6] = dice[5]; tmpdice[2] = dice[6];
		tmpdice[5] = dice[1]; tmpdice[1] = dice[2];
		tmpdice[3] = dice[3]; tmpdice[4] = dice[4];
		for (int i = 1; i < 7; i++) dice[i] = tmpdice[i];
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> M >>x>>y>>K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> jido[i][j];
		}
	}
	int command;
	for (int i = 0; i < K; i++) {
		cin >> command;
		if (x + dx[command] < 0 || x + dx[command] >= N || y + dy[command] < 0 || y + dy[command] >= M) continue;
		movedice(command);
		if (jido[x + dx[command]][y + dy[command]] == 0) {
			jido[x + dx[command]][y + dy[command]] = dice[6];
		}
		else {
			dice[6] = jido[x + dx[command]][y + dy[command]];
			jido[x + dx[command]][y + dy[command]] = 0;
		}
		x += dx[command]; y += dy[command];
		cout << dice[1] << "\n";
	}
	return 0;
}

www.acmicpc.net/problem/15683

1. 풀이방법.

- 전 깊이우선탐색(DFS)로 구현하여 해결하였습니다.

- 깊이우선 탐색을 통해 결국 모든 경우의 수를 모두 확인하는 방식입니다.

- 먼저 카메라를 carr벡터에 입력받을 때 모두 저장해 놓은뒤

- 1번카메라 부터 보면서 1번카메라가 북쪽을 비출 때 -> (깊이 1증가)-> 2번카메라가 어딘가 비출떄.... ->

- 종료조건은 모든 카메라가 어딘가를 비추고 있을 때 입니다.

2. 주의사항 .

- 비춘후 다시 맵의 수정한 부분을 0으로 고쳐줬는데 그때 vector를 잘못사용해서 잠시 오류를 겪었습니다.

3. 나의코드.

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

int N, M;
int cctvmap[8][8];
struct cctv {
	int x; int y; int num;
};
vector<cctv> carr;
int dx[4] = { -1,0,1,0 }; //북동남서
int dy[4] = { 0,1,0,-1 };

void inputs() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> cctvmap[i][j];
			if (cctvmap[i][j] == 6) continue;
			else if (cctvmap[i][j] == 0) continue;
			else { //1,2,3,4,5
				cctv tc; tc.x = i; tc.y = j; tc.num = cctvmap[i][j];
				carr.push_back(tc);
			}
		}
	}
}
int minresult = 64;

void countzero() {
	int resultzero = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (cctvmap[i][j] == 0) resultzero++;
		}
	}
	if (resultzero < minresult) minresult = resultzero;
}

void findzero(int countcctv) {
	if (countcctv == carr.size()) {
		countzero();
		 return;
	}
	for (int i = countcctv; i < carr.size(); i++) {
		if(carr[i].num==1){
			for (int j = 0; j < 4; j++) {
				vector<pair<int, int>> tmpvector;
				int tmpx = carr[i].x; int tmpy = carr[i].y;
				while (1) {
					if (tmpx < 0 || tmpx >= N || tmpy < 0 || tmpy >= M||cctvmap[tmpx][tmpy]==6) { break; } //범위를 넘거나 벽이거나
					if (cctvmap[tmpx][tmpy] == 0) {
						cctvmap[tmpx][tmpy] = 7;
						pair<int, int> tmpp; tmpp.first = tmpx; tmpp.second = tmpy;
						tmpvector.push_back(tmpp);
					}
					tmpx += dx[j]; tmpy += dy[j]; //그 방향으로 계속 전진
				}
				findzero(i + 1);
				for (int k = 0; k < tmpvector.size(); k++) { //다시 맵을 원상태로
					cctvmap[tmpvector[k].first][tmpvector[k].second] = 0;
				}
				tmpvector.clear();
			}
		}
		else if (carr[i].num == 2) {
			for (int j = 0; j < 2; j++) {
				vector<pair<int, int>> tmpvector;
				int tmpx = carr[i].x; int tmpy = carr[i].y;
				while (1) {
					if (tmpx < 0 || tmpx >= N || tmpy < 0 || tmpy >= M || cctvmap[tmpx][tmpy] == 6) { break; } //범위를 넘거나 벽이거나
					if (cctvmap[tmpx][tmpy] == 0) {
						cctvmap[tmpx][tmpy] = 7;
						pair<int, int> tmpp; tmpp.first = tmpx; tmpp.second = tmpy;
						tmpvector.push_back(tmpp);
					}
					tmpx += dx[j]; tmpy += dy[j]; //그 방향으로 계속 전진
				}
				tmpx = carr[i].x; tmpy = carr[i].y;
				while (1) {
					if (tmpx < 0 || tmpx >= N || tmpy < 0 || tmpy >= M || cctvmap[tmpx][tmpy] == 6) { break; } //범위를 넘거나 벽이거나
					if (cctvmap[tmpx][tmpy] == 0) {
						cctvmap[tmpx][tmpy] = 7;
						pair<int, int> tmpp; tmpp.first = tmpx; tmpp.second = tmpy;
						tmpvector.push_back(tmpp);
					}
					tmpx += dx[j+2]; tmpy += dy[j+2]; //그 방향으로 계속 전진
				}
				findzero(i + 1);
				for (int k = 0; k < tmpvector.size(); k++) { //다시 맵을 원상태로
					cctvmap[tmpvector[k].first][tmpvector[k].second] = 0;
				}
				tmpvector.clear();
				}
			}
		else if(carr[i].num==3){
			for (int j = 0; j < 4; j++) {
				vector<pair<int, int>> tmpvector;
				int tmpx = carr[i].x; int tmpy = carr[i].y;
				while (1) {
					if (tmpx < 0 || tmpx >= N || tmpy < 0 || tmpy >= M || cctvmap[tmpx][tmpy] == 6) { break; } //범위를 넘거나 벽이거나
					if (cctvmap[tmpx][tmpy] == 0) {
						cctvmap[tmpx][tmpy] = 7;
						pair<int, int> tmpp; tmpp.first = tmpx; tmpp.second = tmpy;
						tmpvector.push_back(tmpp);
					}
					tmpx += dx[j]; tmpy += dy[j]; //그 방향으로 계속 전진
				}
				tmpx = carr[i].x; tmpy = carr[i].y;
				while (1) {
					if (tmpx < 0 || tmpx >= N || tmpy < 0 || tmpy >= M || cctvmap[tmpx][tmpy] == 6) { break; } //범위를 넘거나 벽이거나
					if (cctvmap[tmpx][tmpy] == 0) {
						cctvmap[tmpx][tmpy] = 7;
						pair<int, int> tmpp; tmpp.first = tmpx; tmpp.second = tmpy;
						tmpvector.push_back(tmpp);
					}
					tmpx += dx[(j+1)%4]; tmpy += dy[(j+1)%4]; //그 방향으로 계속 전진

				}
				findzero(i+ 1);
				for (int k = 0; k < tmpvector.size(); k++) { //다시 맵을 원상태로
					cctvmap[tmpvector[k].first][tmpvector[k].second] = 0;
				}
				tmpvector.clear();
			}
		}
		else if(carr[i].num==4){
			for (int j = 0; j < 4; j++) {
				vector<pair<int, int>> tmpvector;
				int tmpx = carr[i].x; int tmpy = carr[i].y;
				while (1) {
					if (tmpx < 0 || tmpx >= N || tmpy < 0 || tmpy >= M || cctvmap[tmpx][tmpy] == 6) { break; } //범위를 넘거나 벽이거나
					if (cctvmap[tmpx][tmpy] == 0) {
						cctvmap[tmpx][tmpy] = 7;
						pair<int, int> tmpp; tmpp.first = tmpx; tmpp.second = tmpy;
						tmpvector.push_back(tmpp);
					}
					tmpx += dx[j]; tmpy += dy[j]; //그 방향으로 계속 전진

				}
				 tmpx = carr[i].x;tmpy = carr[i].y;
				while (1) {
					if (tmpx < 0 || tmpx >= N || tmpy < 0 || tmpy >= M || cctvmap[tmpx][tmpy] == 6) { break; } //범위를 넘거나 벽이거나
					if (cctvmap[tmpx][tmpy] == 0) {
						cctvmap[tmpx][tmpy] = 7;
						pair<int, int> tmpp; tmpp.first = tmpx; tmpp.second = tmpy;
						tmpvector.push_back(tmpp);
					}
					tmpx += dx[(j+1)%4]; tmpy += dy[(j+1)%4]; //그 방향으로 계속 전진

				}
				 tmpx = carr[i].x; tmpy = carr[i].y;
				while (1) {
					if (tmpx < 0 || tmpx >= N || tmpy < 0 || tmpy >= M || cctvmap[tmpx][tmpy] == 6) { break; } //범위를 넘거나 벽이거나
					if (cctvmap[tmpx][tmpy] == 0) {
						cctvmap[tmpx][tmpy] = 7;
						pair<int, int> tmpp; tmpp.first = tmpx; tmpp.second = tmpy;
						tmpvector.push_back(tmpp);
					}
					tmpx += dx[(j + 2) % 4]; tmpy += dy[(j + 2) % 4]; //그 방향으로 계속 전진

				}
				findzero(i + 1);
				for (int k = 0; k < tmpvector.size(); k++) { //다시 맵을 원상태로
					cctvmap[tmpvector[k].first][tmpvector[k].second] = 0;
				}
				tmpvector.clear();
			}
		}
		else { //5
		vector<pair<int, int>> tmpvector;
		int tmpx = carr[i].x; int tmpy = carr[i].y;
		while (1) {
			if (tmpx < 0 || tmpx >= N || tmpy < 0 || tmpy >= M || cctvmap[tmpx][tmpy] == 6) { break; } //범위를 넘거나 벽이거나
			if (cctvmap[tmpx][tmpy] == 0) {
				cctvmap[tmpx][tmpy] = 7;
				pair<int, int> tmpp; tmpp.first = tmpx; tmpp.second = tmpy;
				tmpvector.push_back(tmpp);
			}
			tmpx += dx[0]; tmpy += dy[0]; //그 방향으로 계속 전진

		}
		tmpx = carr[i].x; tmpy = carr[i].y;
		while (1) {
			if (tmpx < 0 || tmpx >= N || tmpy < 0 || tmpy >= M || cctvmap[tmpx][tmpy] == 6) { break; } //범위를 넘거나 벽이거나
			if (cctvmap[tmpx][tmpy] == 0) {
				cctvmap[tmpx][tmpy] = 7;
				pair<int, int> tmpp; tmpp.first = tmpx; tmpp.second = tmpy;
				tmpvector.push_back(tmpp);
			}
			tmpx += dx[1]; tmpy += dy[1]; //그 방향으로 계속 전진

		}
		tmpx = carr[i].x; tmpy = carr[i].y;
		while (1) {
			if (tmpx < 0 || tmpx >= N || tmpy < 0 || tmpy >= M || cctvmap[tmpx][tmpy] == 6) { break; } //범위를 넘거나 벽이거나
			if (cctvmap[tmpx][tmpy] == 0) {
				cctvmap[tmpx][tmpy] = 7;
				pair<int, int> tmpp; tmpp.first = tmpx; tmpp.second = tmpy;
				tmpvector.push_back(tmpp);
			}
			tmpx += dx[2]; tmpy += dy[2]; //그 방향으로 계속 전진

		}
		tmpx = carr[i].x;tmpy = carr[i].y;
		while (1) {
			if (tmpx < 0 || tmpx >= N || tmpy < 0 || tmpy >= M || cctvmap[tmpx][tmpy] == 6) { break; } //범위를 넘거나 벽이거나
			if (cctvmap[tmpx][tmpy] == 0) {
				cctvmap[tmpx][tmpy] = 7;
				pair<int, int> tmpp; tmpp.first = tmpx; tmpp.second = tmpy;
				tmpvector.push_back(tmpp);
			}
			tmpx += dx[3]; tmpy += dy[3]; //그 방향으로 계속 전진
		}
		findzero(i + 1);
		for (int k = 0; k < tmpvector.size(); k++) { //다시 맵을 원상태로
			cctvmap[tmpvector[k].first][tmpvector[k].second] = 0;
		}
		tmpvector.clear();
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	findzero(0);
	cout << minresult << "\n";
	return 0;
}

www.acmicpc.net/problem/14503

1. 풀이방법.

- 문제의 조건대로 차례로 구현을 해주면 되며,

- 문제에서 첫행,첫열,끝행,끝열은 모두 벽이다 라는 조건도 맞추어 주었으므로 경계의 범위도 신경쓰지 않아도 되서

- 매우 편한 문제였습니다.

- 저 같은 경우 3,4 번의 종료조건을 먼저 체크해주고 그것의 결과에따라 변동을 주는 쪽으로 코드를 짰습니다.

2. 주의사항

- 딱히 없습니다. (저는 청소할 구역은 0, 벽은 1, 청소한 구역은 2 로 설정하였습니다.)

3.나의코드

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

int dx[4] = { -1,0,1,0 }; //북동남서
int dy[4] = { 0,1,0,-1 }; //0,1,2,3
int N, M;
int rx, ry, rd;
int robomap[51][51]; //빈칸은 0, 벽은 1
int cleancount;

void inputs() {
	cin >> N >> M;
	cin >> rx >> ry >> rd;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> robomap[i][j];
		}
	}
}

void cleanroom() {
	while (1) {
		if (robomap[rx][ry] == 0) {
			robomap[rx][ry] = 2; //청소
			cleancount++;
		}
		bool lastcheck = false;
		for (int i = 0; i < 4; i++) {//종료조건 검사
			if (robomap[rx + dx[i]][ry + dy[i]] == 0) { lastcheck = true; break; }
		}
		if (lastcheck == false) {
			if (robomap[rx + dx[(rd + 2) % 4]][ry + dy[(rd + 2) % 4]] == 1) { 
				cout << cleancount << "\n"; break;
			}
			else {
				rx += dx[(rd + 2) % 4]; ry += dy[(rd + 2) % 4];
			}
		}
		else if (lastcheck == true) {
			while (1) {
				if (robomap[rx + dx[(rd + 3) % 4]][ry + dy[(rd + 3) % 4]] == 0) {
					rd = (rd + 3) % 4;
					rx += dx[rd]; ry += dy[rd];
					break;
				}
				else {
					rd = (rd + 3) % 4;
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	cleanroom();

	return 0;
}

www.acmicpc.net/problem/2840

1. 풀이방법 

- 구현자체는 어렵지 않습니다..

- 배열은 ?로 초기화 해주고

- 조건에 따라 INDEX를 취향 껏 조절하시면 됩니다. (방향에 맞춰)

2. 주의사항

- 많이 틀린 이유......예외사항이 중요합니다....

- (1) 같은 문자가 바퀴에 중복으로 붙여져서는 안된다.

- (2) 한 자리에 여러개의 문자가 붙여질 수는 없다.

- 이 떄는 !를 출력해야합니다.

- !!!!! 단, 입력은 돌리면서 상황을 보여주는 것이기 때문에 돌렸을 때 상황이 같은 자리를 가리킬 수도 있기 때문에

- 입력으로 같은 문자가 두번이 들어와도 그것이 같은자리를 가리키고 있는 경우에는 허용이 됩니다...!!

- 이를 조건문에 추가로 걸어주어야 합니다 !

- 너무 쉽다생각했다가 예외처리에서 애좀 먹은 문제입니다...ㅠ

3. 나의코드

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

int N, K;
void setpan(vector<char> &pan) {
	for (int i = 0; i < N; i++) {
		pan[i] = '?';
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> K;
	vector<char> pan(N);
	setpan(pan);
	int index;
	for (int i = 0; i < K; i++) {
		int count; char tmpc;
		cin >> count >> tmpc;
		if (i == 0) { pan[0] = tmpc; index = 0; continue; }
		index = (count + index) % N;
		//돌렸을 때 같은문자(같은 자리)는 나올 수 있다. 그것마저 아니면 틀린 원판
		if (pan[index] != '?'&& pan[index] != tmpc) { cout << "!"; return 0; }
		else {
			pan[index] = tmpc;
		}
	}
	//중복체크
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if(pan[i]!='?' &&pan[i]==pan[j]) { cout << "!"; return 0; }
		}
	}
	for (int i = 0; i < N; i++) {
		cout << pan[index];
		index--;
		if (index == -1) index = N - 1;
	}
	return 0;
}

www.acmicpc.net/problem/14500

1. 문제풀이 방법

- 테트리스에 너무 익숙한 탓일까요....?

- 문제조건에서 대칭을 시켜도 된다는 조건을 빼먹고...이건 뭐 아이디어가 안떠올라서 모든 좌표탐색을 했으나

- 대칭을 안넣었으니...당연히 틀릴 수 밖에 없었습니다....

- 문제 조건을 다시 파악하고 보니 DFS 깊이 4짜리에 해당하는 모든 좌표가 테트로미노로 표현이 된다는 것을

  알아내었습니다....

- 하지만 ㅗ ㅏ ㅜ ㅓ 는 DFS로 표현이 불가능 합니다 (집합느낌으로 보면 테트로미노 > 4짜리 DFS?) 이런느낌?

- 그래서 그건 따로 직접 좌표를 설정해 구해주었습니다.

2. 주의사항

- 문제를 똑바로 파악하자!!!!

3. 나의코드

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

int N, M;
int tetro[501][501];
int maxvalue = 0;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
bool visit[501][501];
int depth = 0;
int tmpsum;

void dfs(int x, int y) {
	if (depth == 4) {
		if (tmpsum > maxvalue) maxvalue = tmpsum;
		return;
	}
	for (int i = 0; i < 4; i++) {
		int x2 = x + dx[i];
		int y2 = y + dy[i];
		if (x2 >= 0 && x2 < N &&y2 >= 0 && y2 < M && visit[x2][y2]==false) {
			visit[x2][y2] = true;
			depth++;
			tmpsum += tetro[x2][y2];
			dfs(x2, y2);
			tmpsum -= tetro[x2][y2];
			depth--;
			visit[x2][y2] = false;
		}
	}
}

void cantdfs(int x, int y)
{
	int result = 0;
	if (x - 1 >= 0 && y + 2 < M) {// ㅗ
		result = tetro[x][y] + tetro[x][y + 1] + tetro[x][y + 2] + tetro[x - 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
	if (x + 1 < N &&y + 2 < M) { // ㅜ
		result = tetro[x][y] + tetro[x][y + 1] + tetro[x][y + 2] + tetro[x + 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
	if (x + 1 < N &&x - 1 >= 0 && y + 1 < M) { // ㅓ
		result = tetro[x][y] + tetro[x][y + 1] + tetro[x - 1][y + 1] + tetro[x + 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
	if (x + 2 < N &&y + 1 < M) {
		result = tetro[x][y] + tetro[x + 1][y] + tetro[x + 2][y] + tetro[x + 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> tetro[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			depth = 1;
			tmpsum = tetro[i][j];
			visit[i][j] = true;
			dfs(i, j);
			visit[i][j] = false;
			cantdfs(i, j);
		}
	}
	cout << maxvalue << "\n";

	return 0;
}

www.acmicpc.net/problem/8980

1. 풀이방법

 - 그리디 문제인데 매우 까다로웠다...

 - 처음에 문제의 설명 방식대로 구현을 하다 보면 반례도 잘 떠오르지 않고 매우 어려웠다...

 - 결국 참고한 게시판의 답변입니다

   (www.acmicpc.net/board/view/6327) 게시판의 plzrun 님의 답변을 보면

 - 왜 도착지를 기준으로 정렬을 해야하는 지를 잘 알 수 있다.

 - 처음 구현한 것도 앞마을 부터 차례대로 박스를 올리는데 뭐가 틀렸지? 를 한참 생각했지만...

 - 문제점은 출발마을을 앞부터 차례대로 기준으로 삼으며 도착지가 가까운 마을 부터 박스를 올린 것이다.

 - 핵심은 1,2,3,... 시작마을부터 차례대로 살피는게 아닌 무조건 도착지가 앞 쪽인 택배박스 부터 올려야 최대의

   양을 배달 할 수 있다.

2. 주의사항

 - 위의 것을 깨닫고도 구현을 생각하는 것도 꽤나 까다로웠습니다..(저는...ㅠㅠ)

 - 문제의 시작부터 마을을 살피는 것으로 생각해서 그 생각에서 벗어나기가;;;

 - 결국 해결한 것은 마을에서의 트럭의 가용용량을 배열로 선언해 저장하고, 박스들을 살펴가며

   마을 별 가용용량을 조절해주는 식으로 구현하였습니다.

3. 나의코드

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

struct box {
	int start;
	int end;
	int weight;
};
int N,C; //마을의 수 , 트럭의 용량
int M; // 박스정보의 수
int x, y, weight;
int result;
int truck[2001]; //마을 별 트럭의 공간을 표시하기 위해서 (트럭에 올라가있는 박스의 상태)

bool compare(box &lhs, box &rhs) {
	if (lhs.end < rhs.end) return true;
	else if (lhs.end == rhs.end) {
		if (lhs.start <= rhs.start) return true;
		else return false;
	}
	else return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> C; //마을 수 와 트럭의 용량
	cin >> M;
	vector<box> sendbox(M);
	for (int i = 0; i < M; i++) {
		cin >> sendbox[i].start >> sendbox[i].end>>sendbox[i].weight;
	}
	sort(sendbox.begin(), sendbox.end(), compare);

	for (int i = 0; i < M; i++) {
		int cnt = 0;
		for (int j = sendbox[i].start; j < sendbox[i].end; j++) {
			cnt = max(truck[j], cnt);
		}
		result += min(sendbox[i].weight, C - cnt); //박스를 올리자 (담을 수 있는 양이 더 적으면 그 만큼만 올릴 수 있다)
		for (int j = sendbox[i].start; j < sendbox[i].end; j++) { //그 만큼 지나가는 마을에서의 트럭의 용량에서 빼줌
			truck[j] += min(sendbox[i].weight, C - cnt);
		}
	}
	cout << result << "\n";
	return 0;
}

www.acmicpc.net/problem/6064

1. 풀이방법

 - M과N이 최대 4000씩입니다. 완전탐색의 경우 시간초과가 뜹니다

 - 멸망의 날 --> 이건 예시가 힌트를 주고 있는데 (10,12) 의 경우 60년이 종말의 년도 입니다

 - (두 수의 최소공배수)라는 게 잘 보이는 예시라서 금방 찾을 수 있었습니다.

 - 어떻게 해야 하나 고민을 하다가 x와y 는 문제에서 보면 M,N으로 증가율?이 나와있고 정해져 있으므로

 - <a,b>라고 할때 a나 b 중 하나를 x나 y 로 고정시켜도 증가율을 알고 있으므로 1씩 증가하며 탐색 시키지 않아도 

 - 알 수 있으므로 하나를 고정 시킵니다.

2. 주의사항

 - N을 넘어갈 때 0으로 초기화 되지 않고 1부터 초기화 되서 시작하므로

   (mod연산의 경우 0~N-1) 이므로 신경써서 MOD연산을 계산합니다

3. 나의코드

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

int T, M, N, x, y;

int GCD(int num1, int num2) { //최대 공약수
	if (num1%num2 == 0) return num2;
	return GCD(num2, num1%num2);
}
int LCM(int num1,int num2){ //최소 공배수
	return (num1*num2) / GCD(num1, num2);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> T;
	while (T--) {
		cin >> M >> N >> x >> y;
		int resultyear = x;
		bool check = false;
		while (1) {
			if (resultyear > LCM(M, N)) { break; }
			if (((resultyear-1)% N) +1 == y) { check = true; break; }
			resultyear += M;
		}
		if (check == true) { cout << resultyear << "\n"; }
		else { cout << -1 << "\n"; }
	}
	return 0;
}

www.acmicpc.net/problem/2887

1. 풀이방법

- 최소신장트리 mst 를 구하는 문제이다.

- 크루스칼 알고리즘을 떠올려서 구현을 했으나 첫 제출결과.....메모리초과.....

- 이 문제에서 사실 크루스칼 알고리즘  자체를 구현하는 것은 매우 쉬웠으나

- 제출 이후 문제 조건을 파악해보니 행성의 수 N개 의 범위가 100,000이다.

- 첫 구현은 모든 간선 (n*(n-1))/2 를 모두 넣고 sorting을 돌렸으니 메모리 초과가 뜰 수 밖에.....

- 그래서 후보가 될 수 있는 간선 자체를 줄이는 방법을 만들어야 했는데, 그 답은

- min(|x1-x2|,|y1-y2|,|z1-z2|) 여기에 있었다.

- 일단 1차원을 가정하고 말해보자 행성이 1,5,6,7,24,36에 있다

- 위치 1에서의 모든 간선은 (1,5), (1,6), (1,7), .... (1,36)까지 인데 이를 모두 볼필요 없이

- 정렬된 상태에서 맞닿은 정점들을 연결하면 이것이 1차원에서의 mst이다 (1-5-6-7-24-36)

- 그렇다면 3차원에서는....? 이렇게 해도 되는건가 머리가 아팠는데...

- 일단 결론은 된다는 것. |x1-x2|에 대해서 정렬후 맞닿은 간선들을 모두 구해서 edge에 넣고

- y와 z에 대해서도 이 작업을 했다.

- 그리고 이 간선을 cost를 기준으로 오름차순 정렬을 해주는데

- 차원을 나눠서 계산을 해도 되는 이유는 예를 들자면 7-24 이 두 행성사이의 x값 차이는 17인데

- 만약 y 나 z 값의 차이에서 더 작은 차이가 있다면 그 간선도 edge 벡터내에 있을 것이고 오름차순 정렬

- 했으므로 먼저 살펴보게 되므로 상관이 없다 뒤에 7-24를 연결하는 간선은 이미 두 정점이 같은 집합 내에 있다면

- 그냥 무시하고 넘어가기 떄문, 그리고 y나 z에서 두 행성이 붙어있지 않다면??? 이라는 의문이 들었는데

- 이 역시 붙어있지 않아 직접적인 간선은 없다고 하더라도 그 사이의 다른 정점과 연결된 간선을 통해서 7-24를 연결

- 하는 간선을 살펴보기 전에 이미 같은 집합에 포함되게 된다.

- 이를 구현한 후 제출했는데 결과는 시간초과.....흠....ㅆ..

- 첫 구현한 코드의 문제점은 그냥 planet 구조체에 각각 key(즉 root) 값을 넣어서 집합이 합쳐질 경우

- 바꿔야할 key값을 가진 정점들을 모두 탐색 해서 바꿔 주게끔 되어있었다.

- 이렇게 되면 후보 간선들을 모두 보는 for문 안에서 또 다른 for문(정점을 모두 탐색하는)

- 이 있었는데 입력이 크니 시간 초과가 날 수 밖에...

- 그래서 결국 key(root) 를 저장하고 있는 vector를 따로 선언해 재귀를 통해 탐색하고 집합의 key값이 바뀌어야 할 

- 경우 탐색해서 찾은 key값만 바꿔주면 되게끔 구현 하였다.

- 여기서의 key(root)값의 의미는 집합의 대표값이다(1번 집합,2번집합...)

2. 주의사항

- 수식을 통해서 간선의 수를 줄일 수 있는 아이디어를 생각하는 것.

- 입력의 규모를 잘 파악하고 구현을 시작할 것.

3. 나의코드

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

int N;
int resultsum;

struct planet { int x, y, z,idx; };
struct edges { int cost, index1, index2; };

vector<planet> parr;
vector<int> rootindex;
vector<edges> earr;


bool cmp(edges a, edges b) {
	if (a.cost < b.cost) return true;
	else return false;
}
bool cmpx(planet a, planet b) {
	if (a.x < b.x) return true;
	else return false;
}
bool cmpy(planet a, planet b) {
	if (a.y < b.y) return true;
	else return false;
}
bool cmpz(planet a, planet b) {
	if (a.z < b.z) return true;
	else return false;
}

int minthree(int n1, int n2, int n3) {
	return min(min(n1, n2),n3);
}

void inputs() {
	cin >> N;
	int tmpx, tmpy, tmpz;
	planet tmpp;
	for (int i = 0; i < N; i++) { //정점삽입
		cin >> tmpx >> tmpy >> tmpz;
		tmpp.x = tmpx; tmpp.y = tmpy; tmpp.z = tmpz; tmpp.idx = i;
		parr.push_back(tmpp);
		rootindex.push_back(i); //처음에 루트는 각자 자기자신
	}
}
int find(int r) {
	if (rootindex[r] == r) return r;
	else { return rootindex[r] = find(rootindex[r]); }
}
void makeedges() { //간선 삽입
	edges tmpe;
	sort(parr.begin(), parr.end(), cmpx); //x 기준으로 오름차순 정렬
	for (int i = 0; i < N-1; i++) {
		tmpe.cost = abs(parr[i].x-parr[i + 1].x);
		tmpe.index1 = parr[i].idx; tmpe.index2 = parr[i + 1].idx;
		earr.push_back(tmpe);
	}
	sort(parr.begin(), parr.end(), cmpy); //y 기준으로 오름차순 정렬
	for (int i = 0; i < N - 1; i++) {
		tmpe.cost = abs(parr[i].y-parr[i + 1].y);
		tmpe.index1 = parr[i].idx; tmpe.index2 = parr[i + 1].idx;
		earr.push_back(tmpe);
	}
	sort(parr.begin(), parr.end(), cmpz); //z 기준으로 오름차순 정렬
	for (int i = 0; i < N - 1; i++) {
		tmpe.cost = abs(parr[i].z-parr[i + 1].z);
		tmpe.index1 = parr[i].idx; tmpe.index2 = parr[i + 1].idx;
		earr.push_back(tmpe);
	}
	sort(earr.begin(), earr.end(), cmp); //cost기준으로 오름차순 정렬
}
void makeMST() {
	int exitcount = 0;
	for (int i = 0; i < earr.size(); i++) {
		if (exitcount == N - 1) break;
		int firstplanet = find(earr[i].index1);
		int secondplanet = find(earr[i].index2);
		if (firstplanet == secondplanet) continue;
		rootindex[secondplanet] = firstplanet;
		resultsum += earr[i].cost;
		exitcount++;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	makeedges();
	makeMST();
	cout << resultsum;
	return 0;
}