대엉코딩

www.acmicpc.net/problem/1406

1. 풀이방법

- 커서가 여러칸씩 뛰는 명령어는 없으므로 상대적으로 간단하였습니다.

- 저는 커서의 앞쪽은 VECTOR 커서의 뒤쪽은 STACK 을 이용하였습니다.

- 방법은 여러가지가 있을 것 같습니다 편하신대로...

- 커서를 왼쪽으로 옮길 때 커서의 뒤쪽이 되는 한 문자는 STACK에 푸쉬하고

- 커서를 오른쪽으로 옮길 때는 STACK에서 POP해 와서 다시 VECTOR에 넣는 식으로 하였습니다.

- 아마 시작할 떄의 커서의 위치가 맨 뒤쪽이라서 이러한 생각을 자연스럽게 하게된 것 같습니다.

2. 주의사항

3. 나의코드

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


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s;
	vector<char> tmpc;
	stack<char> tmps;
	int cursor;
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		tmpc.emplace_back(s[i]);
	}
	cursor = s.length();
	int n;
	cin >> n;
	while (n--) {
		char c;
		cin >> c;
		if (c == 'L') {
			if (cursor == 0) continue;
			else { //커서 뒤쪽은 스택으로 옮겨 놓음
				tmps.push(tmpc[cursor - 1]); tmpc.pop_back(); cursor--;
			}
		}
		else if (c == 'D') {
			if (tmps.empty()) continue;
			else {
				tmpc.emplace_back(tmps.top()); tmps.pop();
				cursor++;
			}
		}
		else if (c == 'B') {
			if (cursor == 0) continue;
			else {
				tmpc.pop_back();
				cursor--;
			}
		}
		else {
			char c;
			cin >> c;
			tmpc.emplace_back(c);
			cursor++;
		}
	}

	//출력부
	for (int i = 0; i < tmpc.size(); i++) {
		cout << tmpc[i];
	}
	while (!tmps.empty()) {
		cout << tmps.top();
		tmps.pop();
	}


	return 0;
}

www.acmicpc.net/problem/10799

1. 풀이방법

- 문제가 요구하는 사항을 구현하는 문제인데, 스택을 이용해서 현재 몇개의 막대가 쌓여있는지를 확인하였습니다.

- 사실 굳이 STACK.SIZE()를 그냥 임의의 변수 하나를 만들어 관리하면 그냥 반복문만으로도 구현 가능합니다.

2. 주의사항

- 조각의 개수가 증가하는 경우는 두가지 경우입니다. 

- (1) 레이저가 자르는 경우 (2) 막대가 끝나는 경우

3. 나의코드

<stack이용>

#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s;
	cin >> s;
	stack<char> sarr;
	int resultnum = 0;
	for (int i = 0; i < s.length(); i++) {
		if (sarr.empty()) { //비어있을 경우
			sarr.push(s[i]); continue;
		}
		if (s[i] == ')'&&s[i-1]== '(') { //레이저
			sarr.pop();
			resultnum += sarr.size();
			continue;
		}
		if (s[i] == '(') { //막대의 시작
			sarr.push(s[i]);
		}
		else if (s[i] == ')') { //막대의 끝
			sarr.pop();
			resultnum++;
		}
	}
	cout << resultnum << "\n";
	return 0;
}

<변수로 관리>

#include<iostream>
#include<string>

	using namespace std;

	int main() {
		int cnt = 0, result = 0;
		string t;
		cin >> t;
		for (int i = 0; i < t.length(); i++) {
			if (t[i] == '(') {
				if (t[i + 1] == ')') {
					i++;
					result += cnt;
					continue;
				}
				cnt++;
			}
			else {
				cnt--;
				result++;
			}
		}
		cout << result;
		return 0;
	}

www.acmicpc.net/problem/1874

1. 풀이방법

- 문제 설명이 약간 부족한 감이 있는데, 예시를 보면서 아 이렇게 하라는 거구나 라고 알게 되었습니다.

- 1~n까지의 숫자를 보는데 입력으로 들어오는 만들어야되는 것들은 큐에 담아 놓고 앞에서 부터 비교를 했습니다.

- 말로 설명이 어려워 아마 코드를 보시면 이해가 쉽게되실듯 합니다.

2. 주의사항

- 이런류의 문제가 사실 꽤 어렵게 느껴집니다. 개인적으로...

- 여러번 풀어봐야 할 것 같습니다.

3. 나의코드

#include<iostream>
#include<stdio.h>
#include<stack>
#include<queue>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, tmp;
	cin >> n;
	queue<int> qar; //만들어야하는 결과
	vector<bool> oper; //결과 출력을 위한 +,- 저장벡터
	stack<int> sar; // 만들기 위해 사용할 스택
	for(int i=0;i<n;i++) {
		cin >> tmp;
		qar.push(tmp);
	}
	for (int i = 1; i <= n; i++) {
		if (i == qar.front()) {
			sar.push(i);
			oper.push_back(1);
			sar.pop();
			oper.push_back(0);
			qar.pop();
			while (1) {
				if (sar.empty() == false) {
					if (sar.top() == qar.front()) {
						sar.pop();
							oper.push_back(0);
							qar.pop();
					}
					else { break; }
				}
				else { break; }
			}
		}
		else {
			sar.push(i);
			oper.push_back(1);
		}
	}
	if(sar.empty()==true){
		for (int i = 0; i < oper.size(); i++) {
			if (oper[i] == 1) {
				cout << '+' << '\n';
			}
			else {
				cout << '-' << '\n';
			}
	    }
	}
	else { cout << "NO" << '\n'; }
	return 0;
}

www.acmicpc.net/problem/16236

1. 풀이방법

- BFS 문제. DFS로도 풀어보았지만 로직은 맞는 것 같지만 역시나 시간 초과가 나옵니다. (코드는 첨부)

- 상어의 위치로 부터 조건에 가장 부합하는 물고기 위치를 BFS로 탐색해 찾아낸 다음

- 그 위치의 물고기를 먹고 상어의크기를 조정이 필요할 경우 해주고 그 위치로 아기상어를 옮겨 주시면 됩니다.

- 저는 DFS를 먼저 풀고 거기서 재활용할 함수들은 재활용하고 makefishcase만 bfs로 바꿔서 구현하여서,

- 불필요한 부분도 들어있습니다. 깔끔하지 않습니다.

2. 주의사항

- 한가지 있는데, 저와 같은 케이스인 분들을 위해 기록합니다.

- bfs로 짰는데 "시간초과" 라는 결과를 얻었습니다.

- 코드를 아무리 봐도 시간초과가 나올만한 연산을 하는 곳이 없습니다.

- 이럴경우 거의 십중팔구 무한루프에 빠지는 테스트케이스가 존재한다는 뜻입니다.

- 그것을 곰곰히 생각해보니, 

- 이러한 경우 입니다

  9 0 0

  4 4 4

  0 0 1

-저의 코드에서는 전체 바다에서 먹을 수 있는 물고기가 존재하는지 체크하는 함수가 있는데,

- 그 함수는 이러한 케이스에서 1이라는 물고기가 있으므로 break;를 걸지 않아서 무한루프에 빠져

- 시간초과가 나오는 것이였습니다.

- 물론 종료조건 함수를 훨씬 정교하고 예쁘게 만드셨다면 해당되지 않으실 수 도 있습니다!

3. 나의코드

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

int dx[4] = { 1,-1,0,0 }; //상하좌우 4방향 탐색
int dy[4] = { 0,0,-1,1 };
int sea[21][21];
bool visit[21][21];
int N;
int resultsecond;
int tmpeat = 0;
int sharksize = 2;
int sharkx, sharky;
int failsecond = -1;

struct fish {
	int x, y, far;
};
vector<fish> farr;
void inputs() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> sea[i][j];
			if (sea[i][j] == 9) { sharkx = i; sharky = j; }
		}
	}
}
bool checksea() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (sea[i][j] > 0 && sea[i][j] < sharksize && sea[i][j] != 9) { return false; }
		}
	}
	return true; //더이상 잡아 먹을 것 이 없음
}
void visitclear() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visit[i][j] = false;
		}
	}
}
queue<fish> tmpq;
void makefishcase(int x, int y) {
	tmpq.push({ x,y,0 });
	int cnt = 0;
	while (1) {
		int si = tmpq.size();
		if (si == 0) { failsecond = resultsecond; break; }
		while (si--) {
			int tx = tmpq.front().x;
			int ty = tmpq.front().y;
			tmpq.pop();
			if (sea[tx][ty] > 0 && sea[tx][ty] < sharksize && sea[tx][ty] != 9) {
				farr.push_back({ tx,ty,cnt });
			}
			for (int i = 0; i < 4; i++) {
				int nextx = tx + dx[i]; int nexty = ty + dy[i];
				if (nextx >= 0 && nextx < N && nexty >= 0 && nexty < N) {
					if (visit[nextx][nexty] == false && sea[nextx][nexty] <= sharksize) {
						visit[nextx][nexty] = true; 
						tmpq.push({ nextx,nexty,0 }); 
					}
				}
			}
		}
		if (farr.empty() == false) break;
		cnt++;
	}
}
bool compare(fish& lh, fish& rh) {
	if (lh.far < rh.far) return true;
	else if (lh.far == rh.far) {
		if (lh.x < rh.x) return true;
		else if (lh.x == rh.x) {
			if (lh.y < rh.y) return true;
			else return false;
		}
		else return false;
	}
	else return false;
}
void queuereset() {
	while (!tmpq.empty()) {
		tmpq.pop();
	}
}
void eatfish() {
	queuereset();
	makefishcase(sharkx, sharky);
	if (failsecond != -1) return;
	sort(farr.begin(), farr.end(), compare); //거리 순 > 위에있는순> 왼쪽에 있는순으로 소팅
	sea[sharkx][sharky] = 0;
	sharkx = farr[0].x; sharky = farr[0].y;
	tmpeat++;
	if (sharksize == tmpeat) {
		tmpeat = 0; sharksize++;
	}
	sea[sharkx][sharky] = 9;
	resultsecond += farr[0].far;
	visitclear();
	farr.clear();
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	while (1) {
		if (checksea()) break;
		visit[sharkx][sharky] = true;
		eatfish();
		if (failsecond != -1) break;
	}
	if (failsecond == -1) {
		cout << resultsecond << "\n";
	}
	else { cout << failsecond << "\n"; }
	return 0;
}

www.acmicpc.net/problem/20061

1. 풀이방법

- 문제의 조건을 그대로 구현하는 문제입니다.

- 문제가 길긴 하지만 테스트케이스 와 문제자체(그림)이 친절하게 나와있어서 과정을 체크하기 편했습니다.

- 딱히 알고리즘을 사용할 건 없고 조건에 맞춘 구현만 해주시면 됩니다.

2. 주의사항

- 두번정도 틀린 후에 정답을 맞췄는데, 첫번째 오답의 경우 도미노를 밀 때 효율적으로 짠다셈 치고 뒤에서 부터

- 탐색을 하면서 도형의 자리를 찾았는데 , 오답이 뜬후 디버깅하며 지도 형태를 보니

- (이러한 경우)

- 0 0 0 1                    1 0 0 1

  0 1 0 1        (--->)   1 1 0 1  (정답)

 이렇게 되어야 하는데,

                                 0 0 1 1

                  (--->)     0 1 1 1 (오답)

- 이러한 실수를 했어서, 앞쪽부터 탐색하는 것으로 바꾸었습니다. (앞으로도 이런문제에서 주의하자..!!)

- 두번째 오답은 도형 유형이 3가지 있는데 테트리스를 생각해 보시면 이게 두줄이 한번에 clear 되는 경우가 발생할 수

- 있습니다. 저 같은 경우 코드 상에서 뒤쪽 부터 탐색 하며 한 행 또는 열 이 클리어 된다면 앞쪽에서 한칸씩 당겨오는

- 방식으로 구현했는데, 이렇게 구현할 경우 땡겨온 다음 그 행 또는 렬 을 한번 더 체크 해주어야 합니다 ( i++ )

- 자세한 것은 주석을 확인해주세요

3. 나의코드

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


int N,t,x,y;
int ground[10][10]; //0~9
int resultscore;
int resultblock;

void fillnemo() {
	if (t == 1) {
		for (int i = 4; i <=9; i++) { //파란색
			if (i == 9) { ground[x][i] = 1; break; }
			if (ground[x][i+1] == 1) { ground[x][i] = 1; break; }
		}
		for (int i = 4; i <= 9; i++) { //초록색
			if (i == 9) { ground[i][y] = 1; break; }
			if (ground[i+1][y] == 1) { ground[i][y] = 1; break; }
		}
	}
	else if (t == 2) {
		int tmpindex=10;
		for (int i = 4; i <= 9; i++) { //파란색
			if (ground[x][i] == 1 ) {
				tmpindex = i;
				break; }
		}
		ground[x][tmpindex - 1] = 1; ground[x][tmpindex - 2] = 1;

		tmpindex = 10;
		for (int i = 4; i <= 9; i++) { //초록색
			if (ground[i][y] == 1||ground[i][y+1]==1) {
				tmpindex = i;
				break;
			}
		}
		ground[tmpindex - 1][y] = 1; ground[tmpindex - 1][y + 1] = 1;
	}
	else {
		int tmpindex = 10;
		for (int i = 4; i <= 9; i++) { //파란색
			if (ground[x][i] == 1 || ground[x + 1][i] == 1) {
				tmpindex = i;
				break;
			}
		}
		ground[x][tmpindex - 1] = 1; ground[x + 1][tmpindex - 1] = 1;
		tmpindex = 10;
		for (int i = 4; i <= 9; i++) { //초록색
			if (ground[i][y] == 1 ) {
				tmpindex = i;
				break;
			}
		}
		ground[tmpindex - 1][y] = 1; ground[tmpindex - 2][y] = 1;
	}
}

void delblock() {
	//파란색
	for (int i = 9; i >= 6; i--) {
		bool checking = false;
		for (int j = 0; j < 4; j++) {
			if (ground[j][i] == 0) { checking = true; break; }
		}
		if (checking == false) { //4블록이 꽉찬경우
			resultscore++;
			for (int k = i; k >= 4; k--) { //이동시키기
				for (int l = 0; l < 4; l++) { ground[l][k] = ground[l][k-1]; }
			}
			i++; // 두줄이 한번에 꽉차는 경우를 위해서 이동시킨후 다시 그 행,렬부터 확인해야됨
		}
	}
	//초록색
	for (int i = 9; i >= 6; i--) {
		bool checking = false;
		for (int j = 0; j < 4; j++) {
			if (ground[i][j] == 0) { checking = true; break; }
		}
		if (checking == false) {
			resultscore++;
			for (int k = i; k >= 4; k--) { //이동시키기
				for (int l = 0; l < 4; l++) { ground[k][l] = ground[k-1][l]; }
			}
			i++; // 두줄이 한번에 꽉차는 경우를 위해서 이동시킨후 다시 그 행,렬부터 확인해야됨
		}
	}
}

void moveblock() { 
	//연한 파란색
	bool checking = false;
	int checkingcount = 0;
	for (int i = 4; i <= 5; i++) {
		for (int j = 0; j < 4; j++) {
			if (ground[j][i] == 1) { checkingcount++; break; }
		}
	}
	if (checkingcount != 0) {
		for (int i = 9; i >= 4; i--) {
			for (int j = 0; j < 4; j++) {
				ground[j][i] = ground[j][i - checkingcount];
			}
		}
	}
	for (int i = 4; i <= 5; i++) {
		for (int j = 0; j < 4; j++) {
			ground[j][i] = 0;
		}
	}
	//연한 초록색
	checking = false;
	checkingcount = 0;
	for (int i = 4; i <= 5; i++) {
		for (int j = 0; j < 4; j++) {
			if (ground[i][j] == 1) { checkingcount++; break; }
		}
	}
	if (checkingcount != 0) {
		for (int i = 9; i >= 4; i--) {
			for (int j = 0; j < 4; j++) {
				ground[i][j] = ground[i-checkingcount][j];
			}
		}
	}
	for (int i = 4; i <= 5; i++) {
		for (int j = 0; j < 4; j++) {
			ground[i][j] = 0;
		}
	}
}
void watchground() {
	cout << endl;
	for (int i = 0; i <= 9; i++) {
		for (int j = 0; j <= 9; j++) {
			cout << ground[i][j];
		}
		cout << endl;
	}
}
void getblock() {
	for (int i = 6; i <= 9; i++) {
		for (int j = 0; j < 4; j++) {
			if (ground[j][i] == true) resultblock++;
		}
	}
	for (int i = 6; i <= 9; i++) {
		for (int j = 0; j < 4; j++) {
			if (ground[i][j] == true) resultblock++;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	while (N--) {
		cin >> t >> x >> y;
		fillnemo(); // 블록 초록색 파란색으로 이동시키기
		delblock(); // 4블록이 꽉찬 행,또는 렬 삭제 (점수 획득)
		moveblock(); // 연한초록, 연한파란색에 블록이 있을 경우 이동
	}
	getblock();
	cout << resultscore << "\n";
	cout << resultblock << "\n";

	return 0;
}

1. 힙 메모리를 사용하는 이유?

- 위의 그림에서 보듯이 heap의 공간과 stack 의 공간에 나누어져 있습니다.

- 그리고 stack메모리의 경우 사용되는 양은 런타임시 결정이 되지만 스택메모리의 최대 공간 (사용가능한) 은 컴파일 시

  이미 지정이 됩니다.

- 왜 스택공간이 있는데 굳이 힙 메모리를 사용해야 하는가 ? 에 대한 궁금증이 떠오르게 됩니다.

- 제가 경험해보고 아는 선에서 몇가지만 이야기해보겠습니다.

-- (1) dynamic (동적할당)

         알고리즘 문제를 풀 때 처럼 입력의 최대값이 정해져 있는경우 그 최대치로 메모리 공간을 할당해서 컴파일 시간

         에 결정을 해서 스택메모리를 사용할 수도 있지만 (큰 사이즈의 경우 다음에 언급), 만약 사용자에 입력에 의해서 

         공간의 변동이 정해지는 경우 개발자 입장에서 미리 그 크기를 예측할 수 없으므로 런타임 시간에 변동에 맞게 

         메모리를 할당해야하는 경우 입니다.

-- (2) size 문제 (엄청 큰)

         이전 게시글에서 언급했다싶이 stack memory의 경우 최대 사이즈가 미리 정해지는 만큼 엄청 큰 사이즈가 필요

         할 경우 stack overflow가 발생할 수 있습니다. 이 때 스택에는 주소를 가리키는 포인터만 설정해주고, heap 메모

         리 공간에 큰 사이즈를 선언해서 가리키게끔 할 수 있습니다.

-- (3) 스택메모리의 life cycle

         스택 메모리의 경우 stack frame단위로 쌓이게 되는데 그 함수가 끝날경우 (life cycle)이 끝날 경우, 스택 메모리에

         서 해제됩니다. 이 경우에도 어떤 데이터를 유지하고 싶을 때는 힙 메모리 공간을 사용합니다. (직접 해제 해주기 

         전 까지 힙 영역에 저장하고 있는 데이터는 사라지지 않으므로)

2. 힙 메모리 사용 in C++

- stack 메모리 대신 heap 메모리를 사용하는 경우는 필요한 용량이 매우 크다던지, dynamic(동적)으로 런타임 시간에

   결정이 되는 변수를 사용한다던지 할 때인데요

- C++에서는 new를 통해서 힙에 공간을 할당 받고 스택 메모리에서의 포인터 변수가 이를 가리키도록 합니다.

- new를 통해서 할당을 받을경우 반드시 까먹지말고 delete을 해주어야만 메모리 leak을 막을 수 있습니다.

- new이외에도 unique_ptr 을 사용한다던지, 배열의 경우 vector를 사용하여 힙에 선언을 해준다면

- 메모리 해제 과정을 신경쓰지 않아도 되게끔 좀 더 안전하게 사용하실 수도 있습니다. 하지만 new를 사용하신다면

- 까먹지말고 반드시 delete으로 해제를 해주어야 한다는 점.!

3. stack 메모리 사용할 때와 heap 메모리 사용할 때의 차이점(장단점?)

- 우선 stack에 선언할 경우 속도가 더 빠릅니다.

- heap의 경우 원하는 만큼의 공간의 힙메모리상에서 찾고 할당하고 나중에는 이를 해제해야 하므로 상대적으로 시간이

- 많이 소요됩니다.

- 그럼에도 heap에는 큰 용량을 필요로 하는 변수라던지, 동적으로 결정이 되는 변수일 때 사용이 가능합니다.

- 그러므로 큰 사이즈가 아닌 경우 (100kb 미만? 정도?) 정도는 속도가 빠른 스택메모리를 사용하는 것이 좋습니다.

- 또 다른 차이점은 스택메모리의 경우 여러번수를 선언하고 주소를 찍어보시면 아시겠지만,

- 빽빽하게?? a가 4바이트를 차지하고, b가 4바이트를 차지한다면 메모리 주소도 4바이트(32bits) 차이가 납니다.

                   (물론 연속되게 위치하고 있을 경우를 가정)

- 중간에 빈 공간없이 빽빽하게 차지하지만, 힙의 경우 구멍이 송송뚤린 것 처럼 사이에 공간이 있습니다.

- 스택처럼 빡빡하게 메모리를 채우지는 않습니다.

www.acmicpc.net/problem/20056

1. 풀이방법

- 구현 문제이고 문제풀이에 필요한 알고리즘은 딱히 없습니다.

- 조건을 파악한뒤 이제 파이어볼이 이동할수 있는 지도가 연결되어 있다는 것이 중요한 것 같습니다.

- N을 넘어가면 다시 1로 오는 것이죠.

- 방향은 친절하게도 지도모양으로 줘서 8방향탐색 dx,dy를 설정해주시면 되고,

- 저같은 경우 파이어볼들을 저장하는 벡터 하나와 각 단계에서 ground[51][51]을 벡터로 선언해서,

- x,y에 이동한 파이어 볼이 있을경우 push_back으로 각 좌표에 매달아주는 느낌으로 구현하였습니다.

- 그렇게 파이어볼이 모두 이동시킨뒤 ground(맵)을 보면서 파이어볼이 없는 좌표는 continue

- 한개있는 좌표는 그대로 다시 totalfireball에 push, 두개 이상인 것은 문제 조건에 맞춰 재조정한후

- 4개의 파이어볼을 다시 totalfireball에 push 해주었습니다.

- 각 단계에서 vector들 clear()를 해주었구요.

2. 주의사항

- 이게 s(속력)이 최대 1000이 될수도 있습니다.

- 그래서 단순히 0보다 작아지면 N을 더해주거나 N보다 커지면 0으로 만들거나 하려면 이 자체도 반복문 처리를 해주어

- 합니다 그래서 그냥 아래와 같이 처리하였습니다.

- int newx = ((totalfireball[i].x) + dx[totalfireball[i].d] * totalfireball[i].s + 250 * N) % N;
  int newy = ((totalfireball[i].y) + dy[totalfireball[i].d] * totalfireball[i].s + 250 * N) % N;

- 250*N을 더해준 이유는 % 모듈러 연산을 할 때 음수가 나오는 것을 방지하기 위함인데

- N의 최솟값은 4이고 s의 최대값은 1000이므로 250*N은 1000보다 같거나 크면서 N 모듈러 연산에는 영향을 끼치지 

- 않는 수로 설정하였습니다(N의배수 이므로)

3. 나의코드

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

int N, M, K;
int dx[8] = { -1,-1,0,1,1,1,0,-1 };//8방향탐색
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };

struct fireball {
	int x,y,m, s, d;
};
vector<fireball> ground[51][51];
vector<fireball> totalfireball;
void inputs() {
	cin >> N >> M >> K;
	int tx, ty, tm, ts, td;
	for(int i=0;i<M;i++){
		cin >> tx >> ty>>tm>>ts>>td;
		totalfireball.push_back({ tx-1,ty-1,tm,ts,td }); // 난 0~N-1
	}
}
void groundclear() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ground[i][j].clear();
		}
	}
}
void moveball() {
	for (int i = 0; i < totalfireball.size(); i++) {
		int newx = ((totalfireball[i].x) + dx[totalfireball[i].d] * totalfireball[i].s + 250 * N) % N;
		int newy = ((totalfireball[i].y) + dy[totalfireball[i].d] * totalfireball[i].s + 250 * N) % N;
		ground[newx][newy].push_back({ newx,newy,totalfireball[i].m,totalfireball[i].s,totalfireball[i].d });
	}
}
void makenewball() {
	for(int i=0;i<N;i++){
		for (int j = 0; j < N; j++) {
			if (ground[i][j].empty()) continue; //비어있으면.
			else if (ground[i][j].size() == 1) { //파이어볼이 한개
				totalfireball.push_back(ground[i][j][0]);
			}
			else { //두개 이상인 경우
				int newm = 0; int news = 0;
				for (int k = 0; k < ground[i][j].size(); k++) {
					newm += ground[i][j][k].m;
					news += ground[i][j][k].s;
				}
				newm = newm / 5;
				if (newm == 0) continue;
				news = news / ground[i][j].size();


				bool check = false;
				for (int k = 0; k < ground[i][j].size(); k++) { //모두 홀수?
					if (ground[i][j][k].d % 2 == 0) { check = true; break; }
				}
				if (check == false) {
					totalfireball.push_back({ i,j,newm,news,0 });

					totalfireball.push_back({ i,j,newm,news,2 });

					totalfireball.push_back({ i,j,newm,news,4 });

					totalfireball.push_back({ i,j,newm,news,6 });
				continue;
				}

				check = false;
				for (int k = 0; k < ground[i][j].size(); k++) { //모두 짝수?
					if (ground[i][j][k].d % 2 == 1) { check = true; break; }
				}
				if (check == false) {
					totalfireball.push_back({ i,j,newm,news,0 });

					totalfireball.push_back({ i,j,newm,news,2 });

					totalfireball.push_back({ i,j,newm,news,4 });

					totalfireball.push_back({ i,j,newm,news,6 });
					continue;
				}
				// 둘다 아닐경우
				totalfireball.push_back({ i,j,newm,news,1 });

				totalfireball.push_back({ i,j,newm,news,3 });

				totalfireball.push_back({ i,j,newm,news,5 });

				totalfireball.push_back({ i,j,newm,news,7 });
			}
		}
	}
}
long long getm() {
	long long resultm = 0;
	for (int i = 0; i < totalfireball.size(); i++) {
		resultm += totalfireball[i].m;
	}
	return resultm;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	while (K--) {
		groundclear();
		moveball();
		totalfireball.clear();
		makenewball();
	}
	cout << getm() << "\n";


	return 0;
}

www.acmicpc.net/problem/20055

1. 풀이방법

- 그냥 조건대로만 구현해 주시면 됩니다.

- 컨베이어 벨트는 문제그대로 N의 최대값인 200을 채우고 INDEX를 그대로 쓰려고 201로 선언해주었고

- bool 타입의 로봇배열을 그의 절반만 선언해서 벨트의 index와 같이 맞추어 위치를 index로 접근하였습니다.

2. 주의사항

- 굳이 이 문제를 블로그에 남기는 데에는 문제설명자체가 얼핏 잘못이해하기 쉬워서입니다.

- 일단 일반적인 우리의 생각으로는 당연히 컨베이어벨트가 한칸움직이면 위의 물건도 따라 움직입니다.

- 그리고 이문제에서는 그와 별개로 로봇도 움직일 수 있다. 라는 것이 이 문제입니다.

- 결국 일반적인 컨베이어벨트의 이동 + 로봇의 이동이 모두 들어간 문제입니다.

- 처음에는 문제의 조건을 읽고 일반적인 컨베이어벨트의 이동에 대한 설명은 없어서 그것을 제외하고 해야하나??

- 벨트는 벨트대로 움직이고 나서, 로봇의 이동을 하는 것인가 생각하였지만 그것은 아니였습니다.

- 물론 테스트케이스가 여러개라서 그것들을 통해서 위의 의문을 걸러낼 수 있습니다.

3. 나의코드

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

int N, K;
int zerocount;
int p = 0;
int barr[201];
bool robo[101];

void ratate() { //barr[0]는 그냥 tmp용으로 사용
	barr[0] = barr[2 * N];
	for (int i = 2 * N; i >= 2; i--) { //벨트이동
		barr[i] = barr[i - 1];
	}
	for (int i = N - 1; i >= 1; i--) { //로봇이동
		robo[i + 1] = robo[i];
	}
	robo[1] = false;
	barr[1] = barr[0];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= 2*N; i++) {
		cin >> barr[i];
		if (barr[i] == 0) zerocount++;
	}
	while (1) {
		if (zerocount >= K) break;
		p++;
		ratate();
		if (robo[N] == true) { //내려오는 칸
			robo[N]= false;
		}
		for (int i = N - 1;  i >= 1; i--) { //이동관련
			if (robo[i] == true) {
				if (robo[i + 1] == false && barr[i + 1] >= 1) {
					robo[i] = false; robo[i + 1] = true;
					barr[i + 1]--;
					if (barr[i + 1] == 0) zerocount++;
				}
			}
		}
		if (robo[1] == false && barr[1] >= 1) { //올라가는 칸
			robo[1] = true; barr[1]--;
			if (barr[1] == 0) zerocount++;
		}
	}
	cout << p << "\n";
	return 0;
}