Be a developer

앞선 1, 2번 문제와 별 차이가 없다. 모든 경우의 수를 다 출력하는 방법이다. solve에 전달할 인자도 필요가 없다. 123456789101112131415161718192021222324252627282930313233#include #include #include #include using namespace std; int n, m;vector v; void solve() { //뽑아야 할 개수만큼 뽑고 나면 출력한다. if (v.size() == m) { for (auto x : v) { printf("%d ", x); } printf("\n"); return; } for (int i = 1; i > n >> m; solve(); return 0;}Colored by Color Scriptercs

N과 M (1) 문제에서 조금만 변형시키면 된다. 오름차순으로 출력해야 하므로, solve 안에서 for 문의 i는 인자인 num보다 1크게 하여 시작한다. 중복은 알아서 걸러지므로 삭제 시켜도 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include #include #include using namespace std; int n, m; vector v; void solve(int num) { //뽑아야 할 개수만큼 뽑고 나면 출력한다. if (v.size() == m) { for (auto x : v) { printf("%d ", x); } printf("\n"..

앞선 재귀 문제들처럼 vector에 원소를 넣을지 말지를 선택하는 선택하는 문제다. vector에 넣은 원소의 개수가 주어진 수와 같을 때 재귀를 종료시키면 된다. 중복해서 뽑지 않도록 check해주는 것만 조심하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #include #include #include using namespace std; int n, m; vector v; bool check(int num) { for (int i = 0; i n >> m; solve(); return 0; } Colored by Co..

앞서 풀어본 1182번 문제를 비트마스크를 이용해 푼다. 명심해야 할 핵심은 부분집합을 '하나의 수'로 나타낸다는 개념이다. {1, 3, 5}를 101010 로 나타내어 42라는 하나의 수로 나타내는 것이다.(2^1 + 2^3 + 2^5 = 42) 집합의 원소 값을 이진수의 자리수로 생각하는 것이다. 즉, 42 = {1, 3, 5} 이다. 해당 문제에서는 집합을 '하나의 수'로 보는 같은 개념을 사용하지만 원소 값 자체를 인덱스로 사용하진 않는다. n이 주어지면 집합에 있는 원소의 개수는 n개가 된다. 이는 '하나의 수'로 치환될 수 있는데, n자리 수의 이진수로 표현할 수 있다. 따라서 모든 부분 집합은 0~(1

연산자 끼워넣기 문제와 똑같다. 다른 점이 있다면 모든 숫자를 다 사용했을 때 함수를 return 시킨다는 것. 각 숫자 사이에 4개의 연산자가 다 들어갈 가능성이 있으므로, 4^(N-1)의 시간복잡도를 갖는다. N이 최대 11이므로 브루트포스로 풀 수 있는 문제이다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include #include using namespace std; vector ans;int n; void solve(int idx, int sum, int plus, int minus, int mult, int div, vector num) { //모든 숫자를 연산에 다 사용하면 return한다. i..

앞에 까지 재귀로 푼 문제들은 하나의 경우를 선택하느냐 선택하지 않느냐 하는 문제였다. 하지만 이번 문제는 연산자 4가지 중 하나를 넣느냐 아니면 넣지 않느냐 하는 문제이기 때문에 경우의 수를 4가지로 나누어서 풀었다. 연산자의 수가 주어진 숫자의 수 보다 1개 적어서 딱 맞기 때문에, 불가능한 경우를 따로 만들어줄 필요가 없다. 재귀의 종료 조건은 연산자의 개수를 다 사용하여 0개가 되는 것이다. minmax_element함수를 사용하는 법을 익숙하게 해야 겠다. auto 연산자를 사용하는 것을 익혀야 한다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include #include using namespace..

sum은 인자로 전달해준다. 중간에 원소 몇 개로 합을 완성할 수도 있지만, 아래 코드에서 sum과 s가 같더라도 이후의 원소가 들어오는 것에 따라서 다시 sum과 s가 같아질 수 있다. 따라서 경우의 수를 (s==sum && i == n)과 (s != sum && i == n) 두 가지로 나누어서 풀어야 한다. 또한 합이 0이 입력되면, 아무것도 선택하지 않아도 0이 되므로, 공집합은 허용되지 않는다. 따라서 답을 출력할 때 1을 빼준다. 123456789101112131415161718192021222324252627282930#include #include #include using namespace std; int n, s;vector v(20);int ans; void go(int i, int ..

이전에 풀었던 로또 문제를 재귀로 푸는 것이다. 이전에는 순열로 풀기위해 선택한 번호는 0으로 넣고, 선택하지 않은 번호는 1로 넣는 새로운 vector를 선언해주었다. 하지만 재귀에서는 앞선 암호 문제처럼 재귀를 통해 넣고, 안 넣고를 할 수 있기 때문에 새로운 vector가 필요없다. 대신 넣고 안 넣고를 check할 check 배열을 하나 생성한다. check 배열을 놓고 풀지 않고, vector하나를 두고 선택하면 vector에 push_back으로 넣고, 넣지 않으면 pop_back으로 빼서 풀 수도 있다. 자세한 설명은 아래 주석으로.. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484..