문제https://www.acmicpc.net/problem/2661 풀이백트래킹을 활용한 문제입니다. 처음에 문제를 보고 정말 많이 헤맸는데, 숫자형으로 표현해야한다는 무의식적인? 고집이 있었습니다. 수열이다보니 숫자로 어떻게 조합을 잘 해야겠다라고 생각한 것이 시간을 많이 잡아먹었습니다. 이 문제에서 포인트가 두 가지가 있다고 생각합니다. 첫 번째는 나타낼 수열을 String으로 받는 것, 그리고 좋은 수열인지 아닌지를 어떻게 판단할지입니다. 전체적인 구조는 백트래킹 메서드의 매개변수를 String 형의 수열로 받아, 좋은 수열이 맞다면 다시 재귀를 돌려주는 방식입니다. 좋은 수열인지를 판단하는 메서드는 String을 subString으로 나누어 반복문을 돌며 구간 검사를 진행하면 됩니..
백트래킹
문제 https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 풀이 순열과 Set 자료구조를 통해 해결했습니다. 우선 N개의 카드 중 K개의 카드를 순서를 고려하여 뽑아야하기 때문에, 순열 백트래킹을 통해 selected[] 배열에 인덱스를 저장합니다. 그리고 card[] 배열에 대입하여 해당하는 카드 번호들을 뽑아냅니다. 이때 번호의 나열은 StringBuilder를 이용해 합치고 그 결과를 Set에 집어넣습니다. Set은 중복을 허용하지 않는 자료구조입니다. 그렇기 때문에 Set의 size를 구하면 중복되지 않은 경우의 수가 나오게 됩니다. 아..
문제 https://www.acmicpc.net/problem/19949 19949번: 영재의 시험 컴퓨터공학과 학생인 영재는 이번 학기에 알고리즘 수업을 수강한다. 평소에 자신의 실력을 맹신한 영재는 시험 전날까지 공부를 하지 않았다. 당연하게도 문제를 하나도 풀지 못하였지만 다행 www.acmicpc.net 풀이 백트래킹을 이용한 문제입니다. 백트래킹 메서드에 매개변수로 찍었는데 맞은 정답의 수, 현재의 인덱스, 찍은 배열을 전달했습니다. 이 때 조건에 따라 정답의 수가 5개가 넘으면 ans++를 통해 답을 구합니다. 그리고 3개 이상 연속된 수를 고를 수는 없다는 조건에 맞게 idx가 2이상일 때는 만약 앞의 idx의 값이 두 번 연속되었다면, 그 수는 다음에서 선택할 수 없도록, ban이라는 변수..
