지구정복

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/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net -문제해설 가능한 조합들 중에서 오름차순으로 출력해야한다. 따라서 dfs 매개변수에 현재 수, 깊이를 넘겨준다. dfs( int index, int depth ) 만약 n = 4, m = 2일 경우 맨 처음 dfs( 1, 0 ) 호출한다. 아래 구문에 의해서 i가 1일 때부터 n(=4)까지 순회한다. for( int i=index; i

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이 ..