https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 감소하는 수 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면 예를 들어, 321, 950. 322, 958 안됨. N번째 감소하는 수를 출력하라. 아랫 자릿수로 갈수록 숫자가 작아지면 되는데, 이때 숫자가 같으면 안 된다. 백트래킹으로 앞 원소의 값보다 크거나 같은 수는 잘라냈다. 1자리부터 10자리까지 BT를 진행했다. 감소하는 수를 구했을 경우, 몇번째 감소하는..

https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 처음에 틀렸던 이유(시간초과)는, 모든 경우의 수를 탐색했기 때문(DFS) 그러나, 모든 경우의 수를 볼 필요가 없다! 조건에 맞지 않는 애는 가지치기 (BackTracking) 이 문제에서는 주어진 부등호에 맞게 숫자를 나열해야 하기 때문에 주어진 부등호를 사이에 넣었을 경우 해당 숫자들이 맞지 않다면 이제 그 경우는 바로 끝이다. 끝까지 갈 필요가 없다! 그러므로, 우선 BT의 종료 조건을 ..

https://www.acmicpc.net/problem/16439 16439번: 치킨치킨치킨 첫 번째 줄에 고리 회원의 수 N (1 ≤ N ≤ 30) 과 치킨 종류의 수 M (3 ≤ M ≤ 30) 이 주어집니다. 두 번째 줄부터 N개의 줄에 각 회원의 치킨 선호도가 주어집니다. i+1번째 줄에는 i번째 회원의 선 www.acmicpc.net 순서대로 정리를 해보자면 1. 치킨 3개 고르기 (backtracking) : vector에 치킨 종류 넣기 2. N명의 만족도 구하기 : 시킨 치킨 3개 중 각 회원의 선호도가 가장 큰 값 3. N개의 만족도를 sum에 누적 합산시키면 answer #include #include #include using namespace std; int n, m, arr[31]..