목록브루트포스 (55)

1일1알

백준 14502번 연구소 C++

백트래킹을 이용하여 벽을 3개를 세운 모든 경우를 구하고 각 경우마다 bfs를 통해 바이러스가 퍼지는 것을 시뮬레이션 한 뒤, 그 중 안전지대가 가장 많이 나온 경우를 출력하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m; vector v(8, vector(8, 0)); vector visited(8, vector(8, false)); int ans = -1; int wall = 3; int posR[4] = { -1,0,1,0 }; int pos..
알고리즘 2021. 12. 28. 12:33
백준 16987번 계란으로 계란치기 C++

백트래킹을 이용하여 가능한 모든 경우를 구하고 그 경우들 중에서 계란이 가장 많이 깨진 개수를 구하면 된다. 처음에 문제를 풀때 현재 잡은 계란의 오른쪽 계란만 깰 수 있다고 생각하고 풀어서 답이 안나왔다. 그래서 문제를 다시 읽어보니 그런 조건이 없어서 모든 경우를 탐색하도록 바꿨더니 문제가 풀렸다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n; vector v(8); int ans = 0; void BT(int index) { if (index >= n..
알고리즘 2021. 12. 23. 12:13
백준 15661번 링크와 스타트 C++

백트래킹으로 문제를 해결하였다. 가능한 링크 팀의 경우의 수를 모두 구하고, 링크 팀의 팀원이 아니라면 스타트 팀에 넣고, 각각의 경우마다 두 팀의 점수의 차의 절댓값 중 가장 작은값을 찾았다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n; vector v(21, vector(21, 0)); vector link; int ans = 987654321; int gap() { int score_link = 0; int score_start = 0; vector..
알고리즘 2021. 12. 20. 11:53
백준 1342번 행운의 문자열 C++

백트래킹을 이용하여 위치를 재배치한 모든 문자열을 구할 수 있다. 첫 번째 예제는 abababa 라는 문자열 하나만 행운의 문자열이지만, 답을 구해보면 144가 나오는데, 그 이유는 abababa 라는 문자가 144번 중복되어서 나오기 때문이다. 이를 해결하기 위해 a의 개수 4, b의 개수 3을 팩토리얼 연산을 하고 곱해준 뒤 답에서 나눠주어야 한다. 4! = 24, 3! = 6이고 24*6 = 144이다. 처음에 구한 답이 144이고 이것을 144로 나누면 1이 나온다. 알파벳의 각각의 개수의 정보를 저장하는 데 unordered_map 자료구조를 사용하였다. #include #include #include #include #include #include #include #include #includ..
알고리즘 2021. 12. 3. 13:01
백준 18428번 감시 피하기 C++

백트래킹을 이용하여 빈 칸에 3개의 장애물을 놓는 모든 경우를 만들고 각각의 경우마다 배열을 검사하면서 하나의 경우라도 선생님의 감시를 피할 수 있다면 YES, 하나도 피할 수 없다면 NO를 출력하도록 구현하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n; char arr[6][6]; bool isPossible = false; int posR[4] = { -1,0,1,0 }; int posC[4] = { 0,1,0,-1 }; bool IsMeet() ..
알고리즘 2021. 11. 27. 14:08
백준 16198번 에너지 모으기 C++

어느 인덱스를 고르면 해당 인덱스의 값은 삭제되고, 그 양 옆의 수의 곱들의 합의 최댓값을 구하는 문제이다. vector의 erase와 insert 기능을 이용하여 재귀 함수로 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; vector v; int res = -1; void solve(int ans) { for (int i = 1; i < v.size() - 1; i++) { int mul = v[i - 1] * v[i + 1]; int delete..
알고리즘 2021. 11. 20. 10:14
이전 Prev 1 ··· 5 6 7 8 9 10 Next 다음