Feel Coding

programmers.co.kr/learn/courses/30/lessons/17682

#include <string>
using namespace std;

int solution(string dartResult) {
    int result[5];
    int temp;
    int index = -1;
    for(int i = 0; i < dartResult.size(); i++) {
        if (dartResult[i] >= '0' && dartResult[i] <= '9') {
            index++;
            if (dartResult[i + 1] == '0') {
                result[index] = 10;
                i++;
            }
            else {
                result[index] = dartResult[i] - '0';
            }
        }
        else if (dartResult[i] == 'D') {
            result[index] *= result[index];
        }
        else if (dartResult[i] == 'T') {
            result[index] *= result[index] * result[index];
        }
        else if (dartResult[i] == '*') {
            result[index] *= 2;
            if (index > 0) {
                result[index - 1] *= 2;
            }
        }
        else if (dartResult[i] == '#') {
            result[index] *= -1;
        }
    }
    return result[0] + result[1] + result[2];
}

programmers.co.kr/learn/courses/30/lessons/17681

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

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    string str = "";
    vector<vector<int>> v1(n, vector<int>(n));
    vector<vector<int>> v2(n, vector<int>(n));
    for(int i = 0; i < n; i++) {
        str += " ";
    }
    for(int i = 0; i < n; i++) {
        int num = arr1[i];
        vector<int> temp;
        while(num > 0) {
            temp.push_back(num % 2);
            num /= 2;
        }
        int index = n - 1;
        for(int j = 0; j < temp.size(); j++) {
            v1[i][index--] = temp[j];
        }
    }
    for(int i = 0; i < n; i++) {
        int num = arr2[i];
        vector<int> temp;
        while(num > 0) {
            temp.push_back(num % 2);
            num /= 2;
        }
        int index = n - 1;
        for(int j = 0; j < temp.size(); j++) {
            v2[i][index--] = temp[j];
        }
    }
    vector<string> answer(n, str);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if (v1[i][j] == 1 || v2[i][j] == 1) {
                answer[i][j] = '#';
            }
        }
    }
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/17676

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

int solution(vector<string> lines) {
    int answer = 0;
    int maxCount = 0;
    for(int i = 0; i < lines.size(); i++) {
        string hours = lines[i].substr(11, 2);
        string minutes = lines[i].substr(14, 2);
        string seconds = lines[i].substr(17, 2);
        string milliseconds = lines[i].substr(20, 3);
        int iMillisecond = stoi(milliseconds) + stoi(seconds) * 1000 + stoi(minutes) * 60 * 1000 + stoi(hours) * 60 * 60 * 1000;
        int cnt = 1;
        for(int j = i + 1; j < lines.size(); j++) {
            hours = lines[j].substr(11, 2);
            minutes = lines[j].substr(14, 2);
            seconds = lines[j].substr(17, 2);
            milliseconds = lines[j].substr(20, 3);
            int jMillisecond = stoi(milliseconds) + stoi(seconds) * 1000 + stoi(minutes) * 60 * 1000 + stoi(hours) * 60 * 60 * 1000;
            string timeString = "";
            for(int k = 24; ; k++) {
                if (lines[j].substr(k, 1) == "s") {
                    break;
                }
                else if (lines[j].substr(k, 1) == ".") {
                    continue;
                }
                timeString += lines[j].substr(k, 1);
            }
            while(true) {
                if (timeString.size() == 4) break;
                timeString += "0";
            }
            int startTime = jMillisecond - stoi(timeString) + 1;
            if (startTime - iMillisecond <= 999) {
                cnt++;
            }
        }
        if (cnt > maxCount) {
            maxCount = cnt;
        }
    }
    return maxCount;
}

programmers.co.kr/learn/courses/30/lessons/17679

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

vector<string> arr;
int cnt = 0;
int width;
int height;

int erase() {
	int eraseCount = 0;
	vector<vector<bool>> check(height, vector<bool>(width, false));
	for (int i = 0; i < height - 1; i++) {
		for (int j = 0; j < width - 1; j++) {
			if (arr[i][j] == arr[i + 1][j] && arr[i][j] == arr[i][j + 1] && arr[i][j] == arr[i + 1][j + 1]) {
				check[i][j] = true;
				check[i + 1][j] = true;
				check[i][j + 1] = true;
				check[i + 1][j + 1] = true;
			}
		}
	}
	for (int col = 0; col < width; col++) {
		vector<char> tempChar;
		for (int i = height - 1; i >= 0; i--) {
			if (!check[i][col] && arr[i][col] != '0') {
				tempChar.push_back(arr[i][col]);
			}
		}
		int row = height - 1;
		for (int i = 0; i < tempChar.size(); i++) {
			arr[row--][col] = tempChar[i];
		}
		for (int i = 0; i < height - tempChar.size(); i++) {
			if (arr[i][col] != '0') {
				arr[i][col] = '0';
				eraseCount++;
			}
		}
	}
	return eraseCount;
}

int solution(int n, int m, vector<string> board) {
	int answer = 0;
	width = m;
	height = n;
	for (int i = 0; i < board.size(); i++) {
		arr.push_back(board[i]);
	}
	while (true) {
		int result = erase();
		if (result == 0) break;
		cnt += result;
	}
	return cnt;
}

www.acmicpc.net/problem/2805

parametric search를 이용해서 풀었다.

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

int main() {
	static long long arr[1000005];
	int n;
	long long m;
	int maxHeight = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (arr[i] > maxHeight) maxHeight = arr[i];
	}
	int start = 0;
	int end = maxHeight;
	long long mid;
	long long total = 0;
	while (start + 1 < end) {
		total = 0;
		mid = (start + end) / 2;
		for (int i = 0; i < n; i++) {
			total += max((long long)0, arr[i] - mid);
		}
		if (total == m) {
			cout << mid;
			return 0;
		}
		else if (total < m) {
			end = mid;
		}
		else if (total > m) {
			start = mid;
		}
 	}
	cout << start;
	return 0;
}

www.acmicpc.net/problem/1011

전에 풀어봤었는데 다시 풀어본다. 전에는 찾아보니까 규칙을 찾아서 풀었었나보다. 근데 그 때는 구글링해서 방법을 알아냈던 것 같고 이번에는 정말 나 스스로 풀었다. 이번에는 반복문을 이용하여 풀었다.

#include <iostream>
using namespace std;

int main() {
	int testCase;
	cin >> testCase;
	int x, y;
	for (int t = 0; t < testCase; t++) {
		cin >> x >> y;
		y = y - x;
		x = 0;
		int location = 0;
		int cnt = 0;
		for (int i = 1; ; i++) {
			if (y - location * 2 == 0) {
				break;
			}
			else if (y - location * 2 <= i) {
				cnt++;
				break;
			}
			else if (y - (location + i) * 2 < 0) {
				cnt += 2;
				break;
			}
			cnt += 2;
			location += i;
		}
		cout << cnt << '\n';
	}
	return 0;
}

www.acmicpc.net/problem/14500

그냥 노가다로 풀면 된다. 특별한 알고리즘 지식이나 기술은 필요없다.

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

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> locationX(19);
	vector<vector<int>> locationY(19);
	locationX[0] = {0, 0, 0, 0};
	locationY[0] = { 0, 1, 2, 3 }; // 가로 일직선
	locationX[1] = { 0, 1, 2, 3 };
	locationY[1] = { 0, 0, 0, 0 }; // 세로 일직선
	locationX[2] = { 0, 0, 1, 1 };
	locationY[2] = { 0, 1, 0, 1 }; // 정사각형
	locationX[3] = { 0, 1, 2, 2 };
	locationY[3] = { 0, 0, 0, 1 }; // └
	locationX[4] = { 0, 0, 0, 1 };
	locationY[4] = { 0, 1, 2, 0 }; // ┌
	locationX[5] = { 0, 0, 1, 2 };
	locationY[5] = { 0, 1, 1, 1 }; // ┐
	locationX[6] = { 0, 0, 0, -1 };
	locationY[6] = { 0, 1, 2, 2 }; // ┘
	locationX[7] = { 0, 0, -1, -2 };
	locationY[7] = { 0, 1, 1, 1 }; // ┘
	locationX[8] = { 0, 0, 0, 1 };
	locationY[8] = { 0, 1, 2, 2 }; // ㄱ
	locationX[9] = { 0, 0, 1, 2 };
	locationY[9] = { 0, 1, 0, 0 }; // ┌
	locationX[10] = { 0, 1, 1, 1 };
	locationY[10] = { 0, 0, 1, 2 }; // ㄴ
	locationX[11] = { 0, 1, 1, 2 };
	locationY[11] = { 0, 0, 1, 1 }; // └┐
	locationX[12] = { 0, 0, -1, -1 };
	locationY[12] = { 0, 1, 1, 2 }; // ┘┌
	locationX[13] = { 0, -1, -1, -2 };
	locationY[13] = { 0, 0, 1, 1 }; // ┌┘
	locationX[14] = { 0, 0, 1, 1 };
	locationY[14] = { 0, 1, 1, 2 }; // ┐└
	locationX[15] = { 0, 0, 0, 1 };
	locationY[15] = { 0, 1, 2, 1 }; // ┬
	locationX[16] = { 0, 0, 0, -1 };
	locationY[16] = { 0, 1, 2, 1 }; // ┴
	locationX[17] = { 0, 1, 2, 1 };
	locationY[17] = { 0, 0, 0, -1 }; // ┤
	locationX[18] = { 0, 1, 2, 1 };
	locationY[18] = { 0, 0, 0, 1 }; // ├
	vector<vector<int>> v(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> v[i][j];
		}
	}
	int maxSum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < 19; k++) {
				int sum = 0;
				for (int l = 0; l < 4; l++) {
					int row = i + locationX[k][l];
					int col = j + locationY[k][l];
					if (row >= 0 && row < n && col >= 0 && col < m) {
						sum += v[row][col];
					}
					else {
						sum = -1;
						break;
					}
				}
				if (sum > maxSum) {
					maxSum = sum;
				}
			}
		}
	}
	cout << maxSum;
	return 0;
}

www.acmicpc.net/problem/17135

재귀를 이용하여 3개를 선택하는 조합을 찾고 그 다음 BFS로 가장 가까이 있는 적을 죽이도록 했다. 가장 가까운 적이 여러 명이라면 왼쪽에 있는 적을 먼저 죽여야 하므로 (열, 행)으로pair를 만들어 벡터 temp에 저장해준 후 정렬을 해주었다. (행, 열)이 아니라 (열, 행)으로 pair를 만든 이유는 정렬 기준을 정해주지 않으면 pair의 첫번째 원소를 기준으로 오름차순 정렬이 되기 때문이다. 그러면 자동으로 가장 왼쪽에 있는 적이 가장 앞에 올 것이다.

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

vector<vector<int>> v;
int n, m, d;
int maxNum = 0;
int dx[4] = { -1, 0, 0 };
int dy[4] = { 0, 1, -1 };

void combination(int num, vector<int> result, vector<bool> visited) {
	if (num == 3) {
		int cnt = 0; // 공격한 적의 명수
		vector<vector<int>> tempV = v;
		for (int r = n; r >= 1; r--) {
			set<pair<int, int>> answer;
			for (int s = 0; s < 3; s++) {
				vector<vector<bool>> visited(r, vector<bool>(m, false));
				queue<tuple<int, int, int>> q;
				q.push(make_tuple(r - 1, result[s], 1));
				int distance = d;
				vector<pair<int, int>> temp;
				while (!q.empty()) {
					tuple<int, int, int> cur = q.front();
					q.pop();
					if (tempV[get<0>(cur)][get<1>(cur)] == 1 && get<2>(cur) <= distance) {
						distance = get<2>(cur);
						temp.push_back(make_pair(get<1>(cur), get<0>(cur)));
					}
					if (!visited[get<0>(cur)][get<1>(cur)]) {
						visited[get<0>(cur)][get<1>(cur)] = true;
						for (int i = 0; i < 3; i++) {
							int row = get<0>(cur) + dx[i];
							int col = get<1>(cur) + dy[i];
							if (row >= 0 && col >= 0 && col < m && !visited[row][col] && get<2>(cur) < distance) {
								q.push(make_tuple(row, col, get<2>(cur) + 1));
							}
						}
					}
				}
				sort(temp.begin(), temp.end());
				if (temp.size() > 0) {
					answer.insert(temp[0]);
				}
			}

			for (set<pair<int, int>>::iterator iter = answer.begin(); iter != answer.end(); iter++) {
				int row = (*iter).second;
				int col = (*iter).first;
				tempV[row][col] = 0;
				cnt++;
			}
		}
		if (cnt > maxNum) {
			maxNum = cnt;
		}
		return;
	}
	for (int i = 0; i < m; i++) {
		if (num == 0) {
			result[num] = i;
			visited[i] = true;
			combination(num + 1, result, visited);
			visited[i] = false;
		}
		else {
			if (result[num - 1] < i) {
				result[num] = i;
				visited[i] = true;
				combination(num + 1, result, visited);
				visited[i] = false;
			}
		}
	}
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> n >> m >> d;
	v = vector<vector<int>>(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> v[i][j];
		}
	}
	combination(0, vector<int>(3), vector<bool>(m, false));
	cout << maxNum;
	return 0;
}

www.acmicpc.net/problem/15684

한 열마다 가로선을 세어봤을 때 가로선의 개수가 홀수인 열이 3개를 넘는다면 3개 이하로 놓아서 원하는 결과를 만들 수 없다. 따라서 바로 -1을 출력하고 프로그램을 종료시킨다.

3개 이하라면 정답이 나올 때까지 조합을 이용해 0개, 1개, 2개, 3개를 선택하도록 한다.

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

int n, m, h, a, b;
vector<vector<int>> v;
int answer = -1;

void combination(int k, int num, vector<vector<bool>> visited, vector<pair<int, int>> result) {
	if (answer != -1) {
		return;
	}
	if (num == k) {
		for (int i = 0; i < k; i++) {
			v[result[i].first][result[i].second] = 1;
		}
		bool flag = true;
		for (int j = 1; j <= n; j++) {
			int now = j;
			for (int i = 0; i < h; i++) {
				if (v[i][now] == 1) {
					now++;
				}
				else if (v[i][now - 1] == 1) {
					now--;
				}
			}
			if (now != j) {
				flag = false;
				break;
			}
		}
		if (flag) {
			answer = k;
		}
		for (int i = 0; i < k; i++) {
			v[result[i].first][result[i].second] = 0;
		}
		return;
	}
	for (int i = 0; i < h; i++) {
		for (int j = 1; j < n; j++) {
			if (!visited[i][j] && v[i][j] == 0) {
				if (num == 0) {
					visited[i][j] = true;
					result[num] = make_pair(i, j);
					combination(k, num + 1, visited, result);
					visited[i][j] = false;
				}
				else {
					if (result[num - 1].first < i && v[i][j - 1] == 0 && v[i][j + 1] == 0) {
						visited[i][j] = true;
						result[num] = make_pair(i, j);
						combination(k, num + 1, visited, result);
						visited[i][j] = false;
					}
					else if (result[num - 1].first == i && result[num - 1].second < j && (j - result[num - 1].second) > 1 && v[i][j - 1] == 0 && v[i][j + 1] == 0) {
						visited[i][j] = true;
						result[num] = make_pair(i, j);
						combination(k, num + 1, visited, result);
						visited[i][j] = false;
					}
				}
			}
		}
	}
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> n >> m >> h;
	v = vector<vector<int>>(h, vector<int>(n + 1));
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		v[a - 1][b] = 1;
	}
	int lineCount = 0;
	for (int j = 1; j < n; j++) {
		int cnt = 0;
		for (int i = 0; i < h; i++) {
			if (v[i][j] == 1) {
				cnt++;
			}
		}
		if (cnt % 2 == 1) {
			lineCount++;
		}
	}
	if (lineCount > 3) {
		cout << -1;
		return 0;
	}
	for (int i = 0; i <= 3; i++) {
		combination(i, 0, vector<vector<bool>>(h, vector<bool>(n + 1)), vector<pair<int, int>>(i));
	}
	cout << answer;
	return 0;
}

www.acmicpc.net/problem/2573

BFS로 풀었다. 일단 빙산을 녹인 후 몇 덩이인지 BFS로 알아보았다. 빙산의 개수가 한 덩이가 아니거나 빙산이 모두 녹았으면 반복문을 빠져나가게 했다.

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

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

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> v(n, vector<int>(m));
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> v[i][j];
			if (v[i][j] != 0) {
				cnt++;
			}
		}
	}
	int answer = 0;
	int year = 0;
	int isSplited = false;
	while (true) {
    	// 빙산 녹이기
		vector<vector<int>> temp = v;
		for (int i = 1; i < n - 1; i++) {
			for (int j = 1; j < m - 1; j++) {
				int zeroCount = 0;
				if (v[i][j] != 0) {
					for (int k = 0; k < 4; k++) {
						int row = i + dx[k];
						int col = j + dy[k];
						if (v[row][col] == 0) {
							zeroCount++;
						}
					}
					temp[i][j] -= zeroCount;
					if (temp[i][j] < 0)
						temp[i][j] = 0;
				}
			}
		}
		v = temp;
        
        // 한 덩이인지 체크하기 위한 BFS (너비우선탐색)
		vector<vector<bool>> visited(n, vector<bool>(m));
		bool out = false;
		for (int i = 1; i < n - 1; i++) {
			for (int j = 1; j < m - 1; j++) {
				if (v[i][j] != 0) { // 이 if문에 들어가서 탐색만 하면 탐색을 끝낸다.
					queue<pair<int, int>> q;
					q.push(make_pair(i, j));
					while (!q.empty()) {
						pair<int, int> cur = q.front();
						q.pop();
						if (!visited[cur.first][cur.second]) {
							visited[cur.first][cur.second] = true;
							for (int i = 0; i < 4; i++) {
								int row = cur.first + dx[i];
								int col = cur.second + dy[i];
								if (v[row][col] != 0) {
									q.push(make_pair(row, col));
								}
							}
						}
					}
					out = true;
					break;
				}
				if (out)
					break;
			}
			if (out)
				break;
		}
		for (int r = 1; r < n - 1; r++) {
			for (int c = 1; c < m - 1; c++) {
				if (v[r][c] != 0 && !visited[r][c]) { // 방문하지 않은 빙산이 있다면
					isSplited = true; // 두 덩어리 이상으로 쪼개졌다는 뜻이다.
					break;
				}
			}
			if (isSplited)
				break;
		}
		year++;
		if (isSplited)
			break;
		bool flag = true;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (v[i][j] != 0) {
					flag = false;
					break;
				}
			}
			if (!flag)
				break;
		}
		if (flag) { // 모두 녹아 빙산이 하나도 없다면 빠져나간다
			break;
		}
	}
	if (!isSplited) {
		cout << 0;
	}
	else cout << year;
	return 0;
}