아주정은's 릴상

이문제를 푸는데 정말 오랜시간이 걸린것같다. 혼자서 풀다가 힘들어서 다른사람의 블로그를 뒤져봤다.

정말 오랜만에 푸는거라 코드도 노가다가 정말 많았다.

이문제는 물고기의 이동이 첫번째 난관이고 상어가 먹는것을 DFS형태로 완전탐색을 해주면 된다.

트리구조로 이루어진다. 전역변수를 max_eat을 두고 큰값이 나오면 갱신해 주는 형태로 했다. 코드가 굉장히 비효율적으로 짜졌지만 직관적이라 이해하는데 도움은 될것같다. 다음에 다시 리팩토링해서 올리면 좋을것같다......

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct fish {
	int x;
	int dir;
};
struct pos {
	int x;
	int y;
};

int max_eat = 0;

int xdir[9] = {0,-1,-1,0,1,1,1,0,-1};
int ydir[9] = {0,0,-1,-1,-1,0,1,1,1};

void dfs(fish board[4][4], int eat_num, int ox, int oy, int nx, int ny) {
	eat_num += board[nx][ny].x;
	board[nx][ny].x = 17;
	if (ox != -1 and oy != -1) {
		board[ox][oy].x = 0;
		board[ox][oy].dir = 0;
	}
	fish temp;
	for (int k = 1; k <= 16; k++) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (board[i][j].x == k) {
					//fish move
					while (1) {
						if (i + xdir[board[i][j].dir] < 0 or i + xdir[board[i][j].dir] >= 4 or j + ydir[board[i][j].dir] < 0 or j + ydir[board[i][j].dir] >= 4) {
							board[i][j].dir = board[i][j].dir+1;
							if (board[i][j].dir == 9)board[i][j].dir = 1;
							continue;
						}
						else if (board[i + xdir[board[i][j].dir]][j + ydir[board[i][j].dir]].x == 17) {
							board[i][j].dir = board[i][j].dir + 1;
							if (board[i][j].dir == 9)board[i][j].dir = 1;

							continue;
						}
						else {
							temp = board[i + xdir[board[i][j].dir]][j + ydir[board[i][j].dir]];
							board[i + xdir[board[i][j].dir]][j + ydir[board[i][j].dir]] = board[i][j];
							board[i][j] = temp;
							goto silver;
						}
					}
				}
			}
		}
	silver:;
	}

	//먹을거 결정
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (board[i][j].x == 17) {
				if (board[i][j].dir == 1) {
					vector<pos> vec;
					if (i - 1 < 0) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_i = i - 1;
					while (1) {
						if (board[t_i][j].x != 0)vec.push_back({ t_i,j });
						t_i--;
						if (t_i < 0)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}

				}
				else if (board[i][j].dir == 2) {
					vector<pos> vec;
					if (i - 1 < 0 or j - 1 < 0) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_i = i - 1, t_j = j - 1;
					while (1) {
						if (board[t_i][t_j].x != 0)vec.push_back({ t_i,t_j });
						t_i--;
						t_j--;
						if (t_i < 0 or t_j < 0)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
				else if (board[i][j].dir == 3) {
					vector<pos> vec;
					if (j - 1 < 0) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_j = j - 1;
					while (1) {
						if (board[i][t_j].x != 0)vec.push_back({ i,t_j });
						t_j--;
						if (t_j < 0)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
				else if (board[i][j].dir == 4) {
					vector<pos> vec;
					if (i + 1 >= 4 or j - 1 < 0) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_i = i + 1, t_j = j - 1;
					while (1) {
						if (board[t_i][t_j].x != 0)vec.push_back({ t_i,t_j });
						t_i++;
						t_j--;
						if (t_i >= 4 or t_j < 0)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
				else if (board[i][j].dir == 5) {
					vector<pos> vec;
					if (i + 1 >= 4) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_i = i + 1;
					while (1) {
						if (board[t_i][j].x != 0)vec.push_back({ t_i, j });
						t_i++;
						if (t_i >= 4)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
				else if (board[i][j].dir == 6) {
					vector<pos> vec;
					if (i + 1 >= 4 or j + 1 >= 4) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_i = i + 1, t_j = j + 1;
					while (1) {
						if (board[t_i][t_j].x != 0)vec.push_back({ t_i,t_j });
						t_i++;
						t_j++;
						if (t_i >= 4 or t_j >= 4)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
				else if (board[i][j].dir == 7) {
					vector<pos> vec;
					if (j + 1 >= 4) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_j = j + 1;
					while (1) {
						if (board[i][t_j].x != 0)vec.push_back({ i,t_j });
						t_j++;
						if (t_j >= 4)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
				else if (board[i][j].dir == 8) {
					vector<pos> vec;
					if (i - 1 < 0 or j + 1 >= 4) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_i = i - 1, t_j = j + 1;
					while (1) {
						if (board[t_i][t_j].x != 0)vec.push_back({ t_i,t_j });
						t_i--;
						t_j++;
						if (t_i < 0 or t_j >= 4)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
			}
		}
	}
}

int main() {
	fish arr[4][4];
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> arr[i][j].x >> arr[i][j].dir;
		}
	}//입력받기
	dfs(arr, 0, -1, -1, 0, 0);
	cout << max_eat << endl;
}

저번에 풀었는데, 런타임에러나서 질문을 올렸었다.

근데 리턴값 안줘서 그런것같다고 그랬다.... 그래서 리턴값 모두 설정해줬더니 됐다.....

그리고 다른사람들이 풀어놓은거 보니깐. 굉장히 sort함수 써서 잘했던데 나는 몰랐다. 

나는 멍청이다. 소팅함수를 구현했다고 보면된다......

#include<iostream>
#include<string>

using namespace std;

string arr[20001];

void initialize(int input) {
	for (int i = 0; i < input; i++) {
		arr[i] = "";
	}
}

void push_back(int start, int end) {
	for (int i = end-1; i >= start; i--) {
		arr[i + 1] = arr[i];
	}
}

bool insert_sort(string input, int num) {
	for (int i = 0; i < num; i++) {
		if (arr[i] == input) {
			return false;
		}
		if (arr[i].length() > input.length()) { //뒤로 미뤄줘야한다.
			push_back(i, num);
			arr[i] = input;
			return true;
		}
		else if (arr[i].length() == input.length()) { //길이가 같다면, 사전순으로 비교
			for (int j = 0; j < input.length(); j++) {
				if (int(arr[i][j]) > int(input[j])) { //입력이 앞설때
					push_back(i, num);
					arr[i] = input;
					return true;
				}
				else if (arr[i][j] < input[j]) {
					break;
				}
			}
		}
	}
	arr[num] = input;
    return true;
}

int main(void) {
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base :: sync_with_stdio(false);
	int T;
	string str;
	cin >> T;
	initialize(T);
	cin >> str;
	arr[0] = str;
	for(int i=1;i<T;i++){
		cin >> str;
		if (insert_sort(str, i) == false) {
			i--;
			T--;
			continue;
		}
	}

	for (int j = 0; j < T; j++) {
		cout << arr[j] << "\n";
	}
    return 0;
}

카페에 왔는데 영어공부하기 시끄러워서 백준 한문제를 풀었다.

문제 링크 : https://www.acmicpc.net/problem/6588

문제가 크게 어렵지는 않았다.

3부터 입력된 숫자까지 돌아가며 찾으면 된다. 

b-a가 가장 큰 값을 찾으라고했는데 그냥 루프 돌다가 찾은게 가장작은 것이기 때문에 찾으면 브레이크하면 끝이다.

지적은 언제나 환영입니다.

#include<iostream>
#include<cmath>

using namespace std;

bool prime_num_discriminator(int input) {
	for (int i = 2; i <= sqrt(input); i++) {
		if (input%i == 0)return false;
	}
	return true;
}

int main(void) {
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base :: sync_with_stdio(false);
	int input = 1;
	int a, b;
	bool suc = false;
	
	while (input) {
		cin >> input;
		for (int i = 1; i < input / 2; i++) {
			a = 2 * i + 1; //홀수
			b = input - a;
			if (prime_num_discriminator(a) and prime_num_discriminator(b)) {
				cout << input << " = " << a << " + " << b << "\n";
				suc = true;
				break;
			}
		}
		if (!suc) cout << "Goldbach's conjecture is wrong\n";
	}
}

문제 링크 : https://www.acmicpc.net/problem/1182 <- 여기

오랜만에 문제를 풀어보았다.

부분 수열의 합인데, 완전탐색으로 할수있다. 하지만 겹치는건 카운팅하면 안된다.

그래서 들어갔던건 빼고 그 뒤에꺼부터 DFS에 넣어주면 된다.

코드를 확인하면 된다.

#include <iostream>

using namespace std;

int arr[20];
int n, s;
int cnt = 0;

void init_arr(int input) {
	for (int i = 0; i < input; i++) {
		arr[i] = 0;
	}
}

void dfs(int sum, int input) {
	
	if (sum == s and input !=0) {
		cnt++;
	}

	if (input == n) return;

	for (int i = input; i < n; i++) {
		dfs(sum + arr[i], i + 1);
	}
}

int main(void) {
	cin >> n >> s;
	init_arr(n);
	

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	dfs(0, 0);
	cout << cnt << endl;
}

테스트케이스 통과한 코드 공유합니더~

지적환영합니다!

vector<string> solution(vector<vector<string>> dataSource, vector<string> tags) {
	vector<string> answer;
	int data_length = dataSource.size();
	int arr[data_length];
	for (int i = 0; i < data_length; i++) {
		arr[i] = 0;
	}

	for (int t = 0; t < tags.size(); t++) {
		for (int i = 0; i < dataSource.size(); i++) {
			for (int j = 1; j < dataSource.size(); j++) {
				if (tags[t] == dataSource[i][j]) {
					arr[i]++;
				}
			}
		}
	}

	for (int j = 0; j < 10; j++) {
		int max = 0;
		int idx;
		for (int i = 0; i < dataSource.size(); i++) {
			if (arr[i] > max) {
				max = arr[i];
				idx = i;
			}
		}//가장 많은 태그 갖고있는 인덱스 구하기
		if (max == 0) break;
		answer.push_back(dataSource[idx][0]);
		arr[idx] = 0;
	}
	return answer;
}

테스트케이스 통과한 코드만 올리겠뜹니다~

트리구조 생각해서 재귀를 사용해서 구현했다.

int solution(string road, int n) {
	int answer = -1;
	int temp = 0;
	int zero_cnt = 0;

	for (int i = 0; i < road.length(); i++) {
		if (road[i] == '0') {
			zero_cnt++;
		}
	}

	if (zero_cnt == 0 or n == 0) {
		int length = 0;
		int max = 0;
		for (int i = 0; i < road.length(); i++) {
			if (road[i] == '1') {
				length++;
			}
			else {
				if (max < length) {
					max = length;
					length = 0;
				}
			}
		}
		if (max < length) {
			max = length;
			length = 0;
		}
		return max;
	}

	for (int i = 0; i < road.length(); i++) {
		if (road[i] == '0') {
			road[i] == '1';
			temp = solution(road, n - 1);
			if (answer < temp) {
				answer = temp;
			}
			road[i] = '0';
		}
	}
	return answer;
}

테스트 케이스만 통과한 코드이지만 기록한다.

난의도는 중간정도 되는것 같다.

int solution(string answer_sheet, vector<string> sheets) {
	int answer = -1;
	int que_num = answer_sheet.length();
	int student_num = sheets.size();
	int max_c_idx = -1;
	for (int i = 0; i < student_num; i++) {
		for (int j = 0; j < student_num; j++) {
			if (i == j) continue;
			//서로 다른학생일때 비교
			int s_cnt = 0; //의심문항
			int len = 0;
			bool be_que = false;
			int max_len = 0;
			int c_idx = 0;

			for (int k = 0; k < que_num; k++) {
				if (sheets[i][k] == sheets[j][k] and sheets[i][k] != answer_sheet[k]) {
					s_cnt++;
					len++;
					if (len > max_len) {
						max_len = len;
					}
				}
				else {
					len = 0;
				}
			}
			c_idx = s_cnt + (max_len*max_len);
			if (c_idx > max_c_idx) {
				max_c_idx = c_idx;
			}
		}
	}
	answer = max_c_idx;

	return answer;
}

경험삼아 본단 마인드로 코딩테스트에 응시했다.

왜냐하면 자소서 안써도 볼수있기 때무니지~~~

테스트 케이스만 통과한 코드인데 이의있다면 답글 부탁합니다~

int solution(string inputString) {
	int answer = 0;
	bool T = false;
	int arr[4] = { 0, 0, 0, 0 };
	for (int i = 0; i < inputString.length(); i++) {
		if (inputString[i] == '(') {
			arr[0]++;
		}
		else if (inputString[i] == '{') {
			arr[1]++;
		}
		else if (inputString[i] == '[') {
			arr[2]++;
		}
		else if (inputString[i] == '<') {
			arr[3]++;
		}
		else if (inputString[i] == ')') {
			if (arr[0] > 0) {
				answer++;
			}
			arr[0]--;
		}
		else if (inputString[i] == '}') {
			if (arr[1] > 0) {
				answer++;
			}
			arr[1]--;
		}
		else if (inputString[i] == ']') {
			if (arr[2] > 0) {
				answer++;
			}
			arr[2]--;
		}
		else if (inputString[i] == '>') {
			if (arr[3] > 0) {
				answer++;
			}
			arr[3]--;
		}

		for (int i = 0; i < 4; i++) {
			if (arr[i] < 0) {
				answer = -1;
				break;
			}
		}
		if (answer == -1) break;
	}
	return answer;
}

내가 어떻게 풀었는지 기록할려고 쓴다.

​문제는 문자열을 받았을때, 문자열을 숫자로 변환하는게 문제다.

그럼 일단 문자열을 입력 받는게 우선이다.

문자열을 입력받고, 문자열을 반복문을 통해 하나하나 읽어 나간다.

경우의 수는 네가지이다. (,),[,] 이렇게 네가지로 나누어서 처리를 해준다.

근데 나는 처음에 ),] 이 닫아주는 문자열이 나올때 숫자를 업데이트 할려고했다.

예를 들면, (()[[]]) = 2*(2+3*(3)) = 22 이다. 그런데 분배법칙으로 풀면 2*2 + 2*3*3 이렇게 나온다.

내 생각이 짧았다. 분배법칙이 가능하기때문에 tmp 변수를 초기에 1로 두고, 괄호를 열어주는 문자가 나오면 곱해주면서 분배법칙이 잘적용될수있는 파라미터를 만든다. 그러다가 닫아주는 문자가 나오면 tmp를 결과값에 더해주고 나눠준다.

그리고 나머지 에러들을 처리해준다. 만약 잘못된물자열이라면 짝이 안맞을 것이다. 스택에서 나오는게 현재 문자와 짝이 안맞을 경우, 문자열이 끝나지 않았는데 스택이 비어버리는 경우, 문자열이 끝났는데 스택에 남아있는 경우가 있을것이다.

솔직히 이해는 되지만 말로 설명하기는 좀 힘들다.

​알고리즘 문제는 많이 풀어보면서 외우는것도 좋은 방법인것같다.

#include <iostream>
#include<stack>
#include<string>

using namespace std;


int main()
{
	int tmp = 1, output = 0;
	string str;
	bool wrong = false;
	stack<char> st;
	cin >> str;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(') {
			st.push('(');
			tmp *= 2;
		}
		else if (str[i] == '[') {
			st.push('[');
			tmp *= 3;
		}

		else if (str[i] == ')') {
			if (st.empty()) {
				wrong = true;
				break;
			}
			if (st.top() == '(') {
				if (str[i - 1] == '(') output += tmp;
				st.pop();
				tmp /= 2;
			}
			else {
				wrong = true;
				break;
			}
		}
		else if (str[i] == ']') {
			if (st.empty()) {
				wrong = true;
				break;
			}
			if (st.top() == '[') {
				if(str[i-1]=='[') output += tmp;
				st.pop();
				tmp /= 3;
			}
			else {
				wrong = true;
				break;
			}
		}
	}

	if (wrong or !st.empty()) {
		cout << 0 << endl;
	}
	else {
		cout << output << endl;
	}
}
​

문제는 굉장히 쉬웠는데, 흠....초기화를 간과했다.

​문제 쉽다고 너무 자만고릴라였다 이거야~

방문했다는 표시 배열을 항상 초기화를 잘해주자.

이것은 그냥 bfs이용해서 풀면 아주쉽다.

​

#include <iostream>
#include<queue>
#include<string>

using namespace std;

struct Que {
	int x;
	int y;
	int z;
	int time;
};

char board[32][32][32];
bool vis[32][32][32];

int dx[6] = {1,-1,0,0,0,0};
int dy[6] = {0,0,1,-1,0,0};
int dz[6] = {0,0,0,0,1,-1};


int main()
{
	
	while (1) {
		int L, R, C;
		string str;
		queue<Que> Q;
		cin >> L >> R >> C;

		if (L == 0 or R == 0 or C == 0)break;

		for (int i = 0; i < L; i++) {
			for (int j = 0; j < R; j++) {
				cin >> str;
				for (int k = 0; k < C; k++) {
					board[i][j][k] = str[k];
					if (board[i][j][k] == 'S') {
						Q.push({ i,j,k,0 });
						vis[i][j][k] = true;
					}
				}
			}
		}

		while (!Q.empty()) {
			auto cur = Q.front();
			Q.pop();
			for (int i = 0; i < 6; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				int nz = cur.z + dz[i];
				if (nx<0 or nx>L - 1 or ny<0 or ny>R - 1 or nz<0 or nz>C - 1)continue;
				if (board[nx][ny][nz] == 'E') {
					cout << "Escaped in " << cur.time + 1 << " minute(s)." << endl;
					goto ijsilver;
				}
				if (board[nx][ny][nz] == '.' and vis[nx][ny][nz] == false) {
					Q.push({ nx,ny,nz,cur.time + 1 });
					vis[nx][ny][nz] = true;
				}
			}
		}

		cout << "Trapped!" << endl;

	ijsilver:
		;

		for (int i = 0; i < L; i++) {
			for (int j = 0; j < R; j++) {
				for (int k = 0; k < C; k++) {
				
					vis[i][j][k] = false;
				}
			}
		}
	}
	
}