https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 이 문제는 BackTracking인데, BFS/DFS의 dx, dy 유형을 가미한 것 같다. BT에서 k개를 선택했으면 ans를 max value로 갱신하고 나가는 기저 조건은 동일한데, 여기서 인접 칸은 선택하면 안 되는 게 관건이다. 이를 위해서, 칸을 선택하기 전에 이 칸의 인접한 칸이 선택되어있는지 체크해줘야 한다. 인접칸이 선택되어있다면 이 칸은 선택하면 안 되기 때문! 선택하..

https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 백트래킹으로 구현하면 되는데, 스타트팀이나 링크팀에 최소 한 명은 들어가야 한다. 그런데 1명만 들어가면 능력치를 구할 수 없다. 그러므로 2명부터~n-3명까지를 한 팀에 넣을 수 있다. for(int i=2; i

https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 이 문제는 삭제, 삽입을 계속해서 하면서 진행해야 한다. 처음에는 x 원소를 지웠다고 치고 배열 인덱스를 넘어가는 방식으로 할까 했는데 어떻게 해야할지 모르겠어서 그냥 vector의 erase, insert 함수를 사용했다. Backtracking을 통해서 1번째 원소와 마지막 원소를 제외한 나머지 원소를 골라서 차례대로 지우면서 양옆 에너지를 모아서 power에 더해주면 된다. #inclu..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 처음에 BFS로 풀다가 답이 제대로 안 나와서 뭐지? 했는데 다시 문제를 읽어보니.. DFS로 풀었어야 했다! 근데 당연함. 한 루트로 쭉 가는 거니까... 멍청하게 시간만 버림.. BFS로ㅋ 내가 넘 좋아하는 BFS 날 배신하다니... 근데 DFS로 막연하게 풀면 안 풀린다. 왜냐면 알파벳 방문 체크를 이미 해줬기 때문에 한 루트만 가고 끝이 나기 때문..!! 여러 루트를 모두 둘러보고 ..

https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 나올 수 있는 모든 수열을 만들어서 나중에 이게 나쁜 수열인지 좋은 수열인지 체크하는 건 시간 초과가 발생한다. 그래서 아무리 생각해도 어떻게 하면 좋을지 모르겠어서 다른 사람들의 코드를 확인했다. 이 분들은 수열을 모두 만들어서 하는게 아니라 하나씩(1,2,3) 붙여나가면서 그때마다 나쁜 수열인지 체크를 했다. 나쁜 수열이면 바로 끝내고 아니면 DFS를 통해서 계속해서 문자를 붙이도록 했다. 그래서 안 되는..

https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net n개 중 k개를 선택해야 한다. 이런 문제는 백트래킹으로 하면 된다. 이 문제는 같은 숫자의 카드가 여러 개여도 중복 숫자를 선택할 수 있다. (같은 카드를 중복 선택은 안됨) 그런데, 그 숫자들로 만들어진 정수가 중복되면 안 된다. 만든 정수가 중복되면 안되니까 간단하게 set를 사용할 수 있다. set 꼭 기억하기!!^^ #include #include #include #include using namespace std; int n, k, arr[11]; set num; bool ch[1..