목록브루트포스 (55)

1일1알

백준 16945번 매직 스퀘어로 변경하기 C++

데이터의 크기가 크지 않기 때문에 백트래킹을 이용하여 모든 경우를 조사해서 매직 스퀘어가 되는 몇 가지 경우를 추출할 수 있다. 처음 입력받은 데이터와 추출한 매직 스퀘어들을 비교해서 바꾸는데 가장 적은 값이 필요한 경우를 찾았다. 그리고 3*3배열이라서 1차원 배열로 관리하는게 더 편할 것 같아서 1차원 배열로 바꿔서 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; vector origin(10); vector visited(10, false); v..
알고리즘 2022. 1. 18. 19:51
백준 16943번 숫자 재배치 C++

a에 있는 숫자들을 백트래킹을 이용하여 새로운 숫자를 만들고, b보다 작은 값들 중 가장 큰 값을 구했다. 처음 시작이 0인 숫자는 제외하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; string a; int b; int ans = -1; vector nums; vector visited(11, false); void BT(int len, int num) { if (len >= nums.size()) { if (num < b) { ans = max(ans, nu..
알고리즘 2022. 1. 17. 09:49
백준 16922번 로마 숫자 만들기 C++

백트래킹을 이용하여 가능한 모든 경우를 구해서 나온 값을 set에 넣는데, 문자의 순서는 상관 없기 때문에 중복을 피하도록 구현했다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n; int values[4] = { 1,5,10,50 }; unordered_set s; void BT(int idx, int cnt, int sum) { if (cnt >= n) { s.insert(sum); return; } for (int i = idx; i < 4; i++) ..
알고리즘 2022. 1. 16. 13:02
백준 2210번 숫자판 점프 C++

1. 백트래킹으로 5번 이동하는 경우를 모두 구한다. 2. 모든 칸에 대하여 1에서 구한 이동하는 경우를 적용한다. 3. 2의 과정에서 6자리수를 만들 수 있으면 그 수를 set에 넣는다. 4. set의 size를 출력한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; vector board(5, vector(5)); vector dirV; set s; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; void Sol..
알고리즘 2022. 1. 16. 12:56
백준 14939번 불 끄기 C++

처음 풀어보는 플래티넘 등급의 문제이다. 푸는 방법을 생각해내는 게 쉽지 않았다. 첫 번째 줄의 전구를 누르거나 누르지 않는 모든 경우 : 2^10 = 1024 이 경우들에서 시작하여 다음 줄에서부터는 자신의 위쪽이 켜져 있으면 끄고, 아니면 넘어간다. = 10) continue; if (nextCol = 10) continue; tmp_board[nextRow][nextCol] = !tmp_board[nextRow][nextCol]; } } void BT(int idx) { if (idx > 9) { bool isAns = true; int cnt = 0; vector tmp_board(10, vector(10)); for (int i = 0; i < 10; i++) { f..
알고리즘 2022. 1. 11. 12:23
백준 18809번 Gaaaaaaaaaarden C++

1. 배양액을 뿌릴 수 있는 땅의 그룹을 만든다. (예제 2의 입력을 예로 들면 (0, 0), (2, 0), (2, 2)) 2. 배양액을 뿌릴 수 있는 땅의 그룹 중 r + g 만큼의 땅의 그룹들을 백트래킹을 이용하여 모두 찾는다. (예제 2의 입력을 예로 들면 g는 2, r는 1이어서 r + g는 3 이기 때문에 1번과 같다.) (만약 g = 1, r = 1 이었다면 r + g = 2 이기 때문에 (0, 0), (2, 0) 과 (0, 0), (2, 2) 과 (2, 0), (2, 2) 세 가지 경우가 나옴) 3. 2에서 찾은 그룹을 r 그룹과 g 그룹으로 나눈다. (예제 2의 입력을 예로 들면 g는 2, r는 1이기 때문에 g : (0, 0), (2, 0) , r : (2, 2) g : (0, 0), (..
알고리즘 2022. 1. 10. 13:32
이전 Prev 1 ··· 3 4 5 6 7 8 9 10 Next 다음