Be a developer

N과 M (2)와 같은 문제이다. 코드를 조금만 수정해주면 된다. 123456789101112131415161718192021222324252627282930313233#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"); return; } for (int i = num; i > n >> m; solve(1); return 0;}Colored by Color Scriptercs

앞선 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

집합을 만드는 문제는 비트 마스크를 통해서 풀 수 있다. 만약 공집합에 1이라는 원소를 추가한다면 이는 0이라는 숫자의 1번 비트에 1을 추가하는 것과 같다. 따라서 집합을 나타내는 변수 ans가 있고, ans가 0이라고 하자. ans |= (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..