반응형 N과 M12 BOJ 15666 : N과 M (12) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15666 N과 M (11)과 동일하지만, 다음으로 올 숫자가 크거나 같아야 하므로, DFS에 start를 이용해서 이전 숫자를 기억하면 된다. #include int N, M; int list[10]; int possible[10000 + 100]; /* 가능한 번호의 수 10000 */ int input[10]; /* input 저장 */ void outputList() { for (int i = 0; i < M;i++) printf("%d ", list[i]); putchar('\n'); } void DFS(int L, int start) { if (L == M) { outputList(); return; } for (int i =.. 2021. 2. 23. BOJ 15665 : N과 M (11) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15665 같은 수를 여러번 골라도 되기 때문에 중복되는 입력은 큰 의미가 없다. 중복되지 않은 총 수를 count하여 N을 바꾸자. 이때, N과 M (10)과 달리, possible은 중복을 체크하는 용도로만 사용한다. int count = 1; for (int i = 1; i 2021. 2. 23. BOJ 15664 : N과 M (10) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15664 다음 Level의 숫자가 크거나 같아야 하므로, start를 추가하기만 하면 된다. N과 M(2)와 N과 M(9)를 참고하자. #include int N, M; int list[10]; int visit[10]; int possible[10000 + 100]; /* 가능한 번호의 수 10000 */ int input[10]; /* input 저장 */ void outputList() { for (int i = 0; i < M;i++) printf("%d ", list[i]); putchar('\n'); } void DFS(int L, int start) { if (L == M) { outputList(); return; } f.. 2021. 2. 23. BOJ 15663 : N과 M (9) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15663 N과 M의 응용 버전이다. N과 M (5)에서 visit 배열을 이용해 번호를 사용했는지 체크했다면, 이제는 visit을 counting해서 가능한 수까지 사용하도록 바꾸면 된다. 예제 입력 2를 보자. 4 2 9 7 9 1 9가 2개, 7이 1개, 1이 1개 있다. 즉, 9는 최대 2번까지 visit으로 카운팅 할 수 있다. 따라서 possible 배열을 만들어서, possible[9] = 2를 저장해두자. 9를 사용하였다면, visit[9]++가 되고, 1 = visit[9] != possible[9] = 2가 되므로, 9를 한번 더 사용할 수 있게 된다. 이때, 입력값 N은 4가 되지만 위와 같이 사용하려면 N = 3으로.. 2021. 2. 23. BOJ 15657 : N과 M (8) - 중복 조합 combination with repetition 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15657 N과 M (5)와 마찬가지로 input에 대해서 N과 M (4)의 코드를 조금만 수정하면 된다. #include int N, M; int list[10]; int input[10]; void outputList() { for (int i = 0; i < M;i++) printf("%d ", list[i]); putchar('\n'); } void DFS(int L, int start) { if (L == M) { outputList(); return; } for (int i = start; i 2021. 2. 22. BOJ 15656 : N과 M (7) - 중복 순열 permutation with repetition 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15656 N과 M (5)와 마찬가지로 input에 대해서 N과 M (3)의 코드를 조금만 수정하면 된다. #include int N, M; int list[10]; int input[10]; void outputList() { for (int i = 0; i < M;i++) printf("%d ", list[i]); putchar('\n'); } void DFS(int L) { if (L == M) { outputList(); return; } for (int i = 1; i 2021. 2. 22. BOJ 15655 : N과 M (6) - 조합 combination 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15655 N과 M (5)와 마찬가지로 input에 대해서 N과 M (2)의 코드를 조금만 수정하면 된다. #include int N, M; int list[10]; int input[10]; void outputList() { for (int i = 0; i < M;i++) printf("%d ", list[i]); putchar('\n'); } void DFS(int L, int start) { if (L == M) { outputList(); return; } for (int i = start; i 2021. 2. 22. BOJ 15654 : N과 M (5) - 순열 permutation 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15654 N과 M (1)은 1~N으로 순열을 출력했다면, 이번엔 특정 input에 대해서 순열을 출력하면 된다. 사전 순으로 증가하는 순서로 출력해야 하므로, input을 입력받고 정렬하자. N이 작기 때문에 단순한 O(N2) 정렬로 해도 큰 무리가 없다. #include int N, M; int list[10]; int visit[10]; int input[10]; /* input 저장 */ void outputList() { for (int i = 0; i < M;i++) printf("%d ", list[i]); putchar('\n'); } void DFS(int L) { if (L == M) { outputList(); ret.. 2021. 2. 22. BOJ 15652 : N과 M (4) - 중복 조합 combination with repetition 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15652 중복 순열에서 순서가 의미가 없다면, 중복 조합이 된다. 중복으로 선택은 가능하되, 다음으로 선택해야할 숫자가 작아서는 안되므로, DFS에 현재 선택한 값을 그대로 넘겨주면, 다음 Level에서는 작은 값을 선택할 수 없게 된다. #include int N, M; int list[10]; void outputList() { for (int i = 0; i < M;i++) printf("%d ", list[i]); putchar('\n'); } void DFS(int L, int start) { if (L == M) { outputList(); return; } for (int i = start; i 2021. 2. 21. 이전 1 2 다음 반응형
