지구정복

https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net -문제해설 1. n, m, arr, sb는 모두 전역변수, n과 m을 입력받는다. 2. dfs메소드 호출. dfs 매개변수는 arr배열에 어느 수부터 저장할 지를 나타내는 start와 dfs메서드의 재귀호출한 횟수(깊이)를 나타내는 depth가 있다. 3. dfs메소드 내부에는 depth == m일 경우 arr배열에 담겨있는 값들을 sb에 append시키고 메서드를 return시켜서 이전 dfs..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net -문제해설 1부터 n까지의 숫자 중에서 m 길이만큼의 수열을 만드는데 오름차순이고 중복되는 숫자가 와도 되는 문제이다. n과 m이 4 4 인 경우 1 1 1 1 1 1 1 2 1 1 1 3 1 1 1 4 1 1 2 1 . . . 4 4 3 4 4 4 4 1 4 4 4 2 4 4 4 3 4 4 4 4 를 출력하면 된다. n=4, m=2라고 가정하자. 1. n과 m을 입력받고 수열을 담을 arr을 ..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net -문제해설 DFS를 이용해서 백트래킹을 구현하면 쉽게 풀 수 있는 문제이다. 처음에 이해가 어려운데 알고보면 간단하다. 예시와 같이 n=4, m=4라고 해보자. 1. n, m 입력받고 출력값을 담을 배열 arr, dfs의 방문처리를 위한 배열 visit를 전역변수로 선언하고 main메서드 안에서 초기화해준다. 2. dfs함수 호출 dfs( n, m, depth ) depth가 m이면, 즉 4이면..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net -문제해설 처음에 dfs로 풀다가 머리가 깨질뻔했다... 욕나오고; 어떻게하면 풀 수는 있을 것 같은데 아직 내 실력이 부족한 것 같다 ㅎ 일단 이 문제를 통해서 최적의 해를 구하는 문제가 나오면 일단은 탐색방법으로 접근을 하고 탐색방법중에서 가능한 방법을 먼저 적용해야겠다는 노하우가 생겼다. 완전탐색이나 이분탐색 등의 방법을 생각하면 될 것 같다. 1. n,m을 입력받는데 m이 ..