대엉코딩

www.acmicpc.net/problem/2422

1. 풀이방법 

- 1~N까지의 모든 아이스크림 중 3개를 만드는 모든 조합을 골라서

- 이게 가능한지 (최악의 조합에 속하는 것이 없는 지) 를 확인 후 방법의 수를 증가시켜 주면되는 문제였습니다.

- 조합을 만드는 것은 어렵지 않았고, 처음에는 최악의 조합을 <pair<int,int>>로 만들어

- 반복문을 통해서 psice() 가능한 아이스크림조합인지를 확인 했었는데, 시간초과가 발생하였습니다.

- 반복문 탐색 중 정지 조건 break 를 걸어 주고 난 뒤 제출해도 역시 시간초과 였습니다.

- 그래서 이차원배열을 선언하여 두 아이스크림이 최악의 조합인지를 O(1) 시간에 확인할 수 있도록

- 수정하여 제출 하였더니 통과 되었습니다.

- 그래프 구현방법 중 인접행렬 방식( 두 노드가 인접했는지 확인하는 것이 매우 빠르다라는 장점)

- 으로 부터 나온 생각으로 구현하였습니다.

2. 주의사항

- 문제 자체는 쉬웠지만, 시간을 단축하는 부분에 있어 특이점이 있는 것 같아 포스팅으로 남깁니다.

3. 나의코드 

- 주석 부분은 반복문을 통한 탐색 부 입니다.

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

int N;
int M;
int t1, t2;
// vector<pair<int, int>> worstice;
bool wi[201][201];
vector<int> icearr;
int pscase = 0;

/*bool psice() {
	for (int i = 0; i < worstice.size(); i++) {
		int tmp = 0;
		for (int j = 0; j < icearr.size(); j++) {
			if (icearr[j] == worstice[i].first || icearr[j] == worstice[i].second) {
				tmp++;
			}
			if (tmp == 2) return false;
			if (icearr[j] > worstice[i].second) break;
		}
	}
	return true;
}*/
bool ps() {
	if (wi[icearr[0]][icearr[1]] == true || wi[icearr[0]][icearr[2]] == true
		|| wi[icearr[1]][icearr[2]] == true) return false;
	else return true;
}

void makeice(int index,int cnt) {
	if (cnt == 3) {
		if (ps()) {
			pscase++;
		}
		return;
	}
	for (int i = index; i <= N; i++) {
		icearr.push_back(i);
		makeice(i+1,cnt + 1);
		icearr.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cout.tie(0); cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> t1 >> t2;
		// worstcase.push_back({t1,t2});
		wi[t1][t2] = true;
		wi[t2][t1] = true;
	}
	makeice(1,0);

	cout << pscase << "\n";

	return 0;
}

www.acmicpc.net/problem/18511

1. 풀이방법

- 처음 문제를 보고 눈에 띈 숫자는 N이 최대 100,000,000 이므로 선형적으로 증가시켜가며 N과 비교하면 시간초과

- 그러면 주어진 집합을 보고 숫자를 구성해서 N과 비교를 해야 겠다.

- 그래서 자릿수 계산하고 앞자리 수 부터 비교를 해 가면서 어떤 원소를 자릿수에 넣고 해야겠다~~ 라면서 하다보니

- 되게 다양한 경우의 수가 있고 생각보다 너무 복잡하였습니다.....하

- 그래서 문제를 다시 읽어보니..... 매우 쉬워지는 이유가 하나 있었습니다 K의 원소의 개수가 최대 3개 라는 것....!

- 저는 K의 집합 원소가 1~9 이고 집합의 원소의 수 도 역시 최대 10개라고 당연시? 생각해서...

- 이 모두를 조합하는 수는 너무 많다 라고 생각했었는데 아니였습니다...

- 최대 3개 이므로 그냥 모든 조합을 만들어 내서 N가 비교하고 N보다 작거나 같을경우의 수를 모두 벡터에 넣고

- 그 중 최대값을 출력하였습니다.

2. 주의사항

- 문제를 똑바로 파악하고 시작할 것 !!!!

3. 나의코드

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

int n, k,tmp;
vector<int> numarr;
vector<int> resultarr; //n을 쪼개놓자

bool compare(int& lhs, int& rhs) {
	if (lhs > rhs) return true;
	else return false;
}

void makecase(int num,int cnt) {
	if (cnt!=0 && num <= n) { 
		resultarr.emplace_back(num);
	}
	if (num > n) return;
	for (int i = 0; i < k; i++) {
		if (cnt == 0) { makecase(num * numarr[i],cnt+1); }
		else makecase(num*10+numarr[i],cnt+1);
	}
}

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

	cin >> n >> k;
	
	for (int i = 0; i < k; i++) {
		cin >> tmp;
		numarr.emplace_back(tmp);
	}
	sort(numarr.begin(), numarr.end(), compare);
	makecase(1,0);
	sort(resultarr.begin(), resultarr.end(), compare);
	cout << resultarr[0];
	return 0;
}

www.acmicpc.net/problem/9663

1. 풀이방법

- N개의 퀸을 놓을 수 있는 경우의 수 를 구하는 문제이고, 모든 경우의 수를 탐색하는데 시간을 신경써야합니다.

- 처음에는 그냥 dx[8],dy[8] 을 선언해서 8방향을 모두 탐색하다가 이미 다른 퀸이 있으면 리턴하고 라는 식으로

- 구현을 했다가.....N=5일때 까지 였나...? 까지 밖에 나오지 않았습니다...

- 처음에 N이 최대 14이길래 시간초과는 신경 안써도 되는 줄 알고 짰다가 당황한 문제였습니다.

- 체스판의 특성을 이용하여 x,y좌표의 특징들을 이용해서 놓을 수 있는지를 판단해야 했습니다.

2. 주의사항

- 체스판의 특성을 활용, 시간초과를 주의해야 함.

- 2차원 배열이 아닌 1차원배열을 이용하여 [x]=y를 통해 x,y 좌표를 나타내는 것이 처음에는 생소할 수 있음

3. 나의코드

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

int N;
int resultcount = 0;
int queenarr[15]; //[x]= y
 // 0~ N-1까지 사용
bool checking(int x, int y) {
	for (int i = 0; i < x; i++) {
		if ( abs(y-queenarr[i]) == abs(x -i) || queenarr[i] == y) {
			return false;
		}
	}
	return true;
}
void makecase(int x) {
	if (x == N) {
		resultcount++; return;
	}
	for (int i = 0; i < N; i++) {
		if (checking(x, i)) {
			queenarr[x] = i;
			makecase(x + 1);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	makecase(0);
	cout << resultcount << "\n";
	return 0;
}

www.acmicpc.net/problem/1620

1. 풀이방법

- 포켓몬도감을 입력받아 찾으면 되는 문제입니다.

- 첫번쨰 문제는 입력이 숫자 일수도, 포켓몬 이름 일수도 있다는 것입니다.

- 이름의 경우 알파벳만으로 이루어져있다고 했으므로, 입력받은 문자열의 첫글자가 알파벳인지 숫자인지만

- 구분해서 구하여주었습니다.

2. 주의사항

- 처음에 그냥 선형탐색으로 짰는데, 이 경우 최대연산 수가 대략 10,000,000,000이 되므로 시간조건을 만족x

- 결국 이분탐색을 이용하고자 하였고 그러려면 알파벳순으로 정렬을 해야 하는데 , 그러면

- index가 섞이기 때문에 따로 알파벳입력이 들어왔을 떄를 위한 index도 가지고 있는 배열을 선언하였습니다.

- 숫자가 들어올 경우 vector<string> 을 통해 index를 구해서 바로 접근 하였고,

- 알파벳으로 들어올 경우 vector<pair<string,int>> 를 정렬해놓은 것을 통해 이분 탐색으로 찾았습니다.

3. 나의코드

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

vector<string> dokam;
vector<pair<string, int>> dokamname; //알파벳이 입력되었을 경우 이분탐색을 위한 !
string tmps;
void find(int bot, int top) {
	if(bot>top) return;
	int mid = (bot + top) / 2;
	if (tmps == dokamname[mid].first) { cout << dokamname[mid].second << '\n'; return; }
	else if (tmps < dokamname[mid].first) { find(bot, mid - 1); }
	else { find(mid + 1, top); }
}
bool compare(pair<string, int> &a, pair<string, int> &b) {
	if (a.first < b.first) return true;
	else return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		dokam.emplace_back(s);
		dokamname.push_back({ s,i });
	}
	sort(dokamname.begin(), dokamname.end(), compare);
	while (m--) {
		int result = 0;
		cin >> tmps;
		if (tmps[0] >= '0'&&tmps[0] <= '9') { //숫자일경우
			int deci = 1;
			for (int i = tmps.length() - 1; i >= 0; i--) {
				result += deci * (int)(tmps[i] - '0');
				deci *= 10;
			}
			cout << dokam[result-1] << "\n";
		}
		else { //선형탐색으로는 시간초과 -> 이분탐색 진행
			find(0,n-1);
		}
	}

	return 0;
}

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;
}