신뇽이 되어보자

https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krclass Solution { //모든 경우의 수를 다 돌아보고 아닐땐 빠져나와야함 dfs, 백트래킹 public int answer; //최대 던전 수 public boolean[] visited; //방문 여부 public int solution(int k, int[][] dungeons) { visited = new boolean[dungeons.length]; //df..

문제N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.입력첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.  예제 입력 4 29 7 9 1예제 출력 1 71 97 9..

문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)출력첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.  쉬움.동전의 가치가 오름 차순으로 주어지기 때문에 도달해야하는 K보다 가치가 작거나 같을 때 뺄 수 있을만큼 최대한 빼주는 것을 반복한다.cnt에 뺀 수를 더해준다. 그러다가..

문제어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 ..

재귀를 이용한 백트래킹을 사용할 것.n이 10 근처일때 사용하기(n이 너무 크면 시간 초과 발생!) 순열순서를 고려하면서 서로 다른 n개에서 중복 없이 r개를 일렬로 나열하는 수시간 복잡도 O(n!) static void permutation(int dept, int n, int r){ //순열이 완성된 경우 if(dept == r){ System.out.println(Arrays.toString(output)); return; } for(int i = 0; i  중복 순열 순서를 고려하면서 서로 다른 n개에서 중복으로 r개를 일렬로 나열하는 수시간 복잡도O(n^r) 방문처리 X static void repeatPermutation(int depth, int n..

구분 : 그리디, 정렬  public class Main { public static void main(String[] args) throws IOException { //2217번 - 로프 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int []w; w = new int[n]; int max = 0; //시간복잡도 O(n) for(int i = 0; i O(n^2) -> 시간 초과가 뜬다.// for(int i = 0; i w..