백트래킹

10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오. 풀이 방향이 있는 그래프에서 한 점에서 출발해서 모든 정점들을 돌고 자신의 정점으로 돌아오는 경우 중에서 최소값을 구하여라 📌 입력 for(int i=1; i

15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 풀이 이전 문제들(15649, 15650)과 다른점은 해당 문제는 연속된 수열이 아닌 주어진 수열을 가지고 새로운 수열을 만드는 것이다. 이때, 수열에 중복된 수가 있을 수 있다는 것이 어려웠다. 만든 수열을 사전순으로 출력해야 하기 때문에 주어진 수열을 sort 메서드로 먼저 정렬한 후 사용했다. ..

1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 풀이 처음에는 부분 수열이 반드시 연속된 수열이여야 하는 줄 잘못 알고 누적합을 사용해서 모든 경우를 탐색하는 방식으로 문제를 해결하려고 했으나 답이 구해지지 않았다. 그래서 질문 게시판을 살펴보니 부분 수열은 연속될 필요가 없고 만약 연속된 부분 수열일 경우 연속이..

15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 풀이 백트래킹을 통해서 이전 depth에서 고른 번호를 체크하고 다음 depth로 진행하면서 모든 경우를 탐색하였다. 📌 백트래킹 탐색 public static void DFS(int depth, String value){ if(depth == M){ sb.append(value.substri..

1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다. A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력하는 프로그램을 작성하시오. 풀이 이전에 백트래킹으로 문제를 풀어보았기 때문에 이번 문제도 한번 백트래킹으로 접근해보았습니다. 4와 7로만 이루어진 수를 만들어야 하기 때문에 현재 자리수에서 뒤에 4, 7를 계속 붙여나가면서 이미 최대 값을 벗어난 수는 더이상 탐색할 필요가 없기 때문에 탐색을 종료..

14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 문제 하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다. 단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다. 돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자! 풀이 해당 문제는 꽃의 씨앗을 심은 기준으로 상, 하, 좌, 우, 현재 위치가 다른 꽃들과 겹치지 않도록 심으면서,..