반응형 백트래킹7 백준 15665번 N과 M (11) - C++ 풀이 1. 숫자를 하나씩 총 M개 뽑는다. 2. 숫자를 뽑을 때는 작은 숫자부터 뽑아본다. 3. 후보 숫자 목록에 중복이 없도록 후보 숫자들을 배열이 아닌 set으로 관리한다. 1. 숫자를 하나씩 총 M개 뽑는다. N개의 후보 숫자 중에서 총 M개 뽑으면 수열이 완성된다. M개를 다 뽑았으면 완성된 수열을 출력해주는 것을 반복한다. 2. 숫자를 뽑을 때는 작은 숫자부터 뽑아본다. 수열을 사전 순으로 증가하는 순서로 완성해야 한다. 따라서 뽑을 때 더 작은 숫자를 먼저 뽑아야 한다. (0으로 시작하는 수열을 1로 시작하는 수열보다 먼저 출력해야 하므로 0부터 뽑아보는 것이다.) 3. 후보 숫자 목록에 중복이 없도록 후보 숫자들을 배열이 아닌 set으로 관리한다. 그런데 중복되는 수열을 출력하면 안된다. 중복되는.. 2023. 8. 3. 백준 2529번 부등호 - C++ 풀이 1. 부등호 조건에 맞게 중복 없이 숫자를 하나씩 뽑는다. 2. k+1개를 다 뽑았으면 최대, 최소 정수를 업데이트한다. 1. 부등호 조건에 맞게 중복 없이 숫자를 하나씩 뽑는다. 백트래킹으로 풀 수 있다. 부등호 조건에 맞으면서 중복 사용이 없도록 숫자를 하나씩 뽑아나간다. 2. k+1개를 다 뽑았으면 최대, 최소 정수를 업데이트한다. 부등호가 k개이므로 총 k+1개의 숫자를 뽑아야 한다. 다 뽑았으면 완성된 정수를 구하여 최대, 최소 정수를 업데이트한다. 이때는 문자열을 활용하면 편하다. #include using namespace std; int k; char signs[10]; int pick[10]; bool is_used[10]; string max_ans = "0000000000", min_.. 2023. 8. 3. 백준 15684번 사다리 조작 - C++ 풀이 1. i번 세로줄과 (i+1)번 세로줄 사이에 가로줄을 놓으면 i와 (i+1)의 위치가 바뀐다. 2. 백트래킹으로 최대 3개의 가로선을 놓는 경우를 모두 시도해본다. 1. i번 세로줄과 (i+1)번 세로줄 사이에 가로줄을 놓으면 i와 (i+1)의 위치가 바뀐다. i번 세로줄과 (i+1)번 세로줄 사이에 가로줄을 놓으면, 원래 결과 (i, i+1)에서 (i+1, i)로 결과가 바뀐다. 두 세로줄의 위치를 스왑한 것과 같은 효과를 얻게 된다. 이 사실을 이용하여 그어진 가로줄의 목록을 가지고 사다리 게임의 결과를 계산할 수 있다. (아래 코드에서 check() 함수 구현을 참고) 2. 백트래킹으로 최대 3개의 가로선을 놓는 경우를 모두 시도해본다. 백트래킹을 이용하여 최대 3개의 가로선을 긋는 경우를 모두 .. 2022. 6. 24. 백준 1405번 미친 로봇 - C++(cpp) 풀이 1. DFS로 모든 경우 4^N가지를 다 고려한다. 2. N칸 모두 이동했을 경우 해당 루트로 이동할 확률을 더한다. 1. DFS로 모든 경우 4^N가지를 다 고려한다. N이 작기 때문에 모든 경우를 다 고려하는 방법을 생각해볼 수 있다. N=14이므로 모든 경우의 수는 4^14 = 268,435,456이 된다. 중간에 방문했던 곳을 또 방문했을 경우 가지치기가 되므로 실제 탐색 횟수는 이것보다 더 적어진다. 2. N칸 모두 이동했을 경우 해당 루트로 이동할 확률을 더한다. N칸을 이동했을 때 해당 루트로 이동할 확률은 매 이동마다 해당 방향으로 이동할 확률의 곱과 같다. dfs에서 매 depth마다 이동 확률을 누적해서 전달해주면 된다. #include #include #include using nam.. 2022. 4. 5. 백준 2580번 스도쿠 - C++(cpp) 풀이 1. 백트래킹으로 빈자리를 차례로 채워나간다. 2. 최초 해답을 찾은 이후에는 더 이상 탐색할 필요가 없으므로 모든 탐색을 리턴으로 종료한다. 1. 백트래킹으로 빈자리를 차례로 채워나간다. 백트래킹 문제이다. 빈칸을 차례로 채워나갈 것이다. 아래 코드에서는 왼쪽 위부터 차례로 채웠다. 어떤 빈칸을 채울 때에는 1~9 중 빈칸에 들어갈 수 있는 수들을 전부 넣어본다. 빈칸에 들어갈 수 있는 수는 같은 행, 열, 블록에 있지 않아야 한다. 2. 최초 해답을 찾은 이후에는 더 이상 탐색할 필요가 없으므로 모든 탐색을 리턴으로 종료한다. 모든 칸을 다 채웠다면 해답을 찾은 것이다. 해답을 찾았는지 여부를 bool 전역 변수로 두고, 해답을 찾으면 이 변수에 기록한다. 이후 모든 탐색은 하지 않아도 되므로, 빈칸.. 2022. 2. 16. 이전 1 2 다음 반응형
