반응형 permutation6 BOJ 17281 : ⚾ (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17281 9명의 타자가 있고 1번 타자는 4번에 고정이므로, 8! = 40320번의 경우의 수에 대해 시뮬레이션을 하면 된다. 9명 타자를 줄 세우는 방법은 N과 M (1) - 순열의 방법을 이용한다. input에서는 간단히 player의 결과를 저장한다. void input() { scanf("%d", &N); for (int i = 1; i 2021. 4. 17. SWEA 5656 : 벽돌 깨기 (모의 SW 역량테스트) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 벽돌 깨기 링크 벽돌은 (1, 1)부터 입력을 받고 주변을 벽(-1)으로 만들어두자. #define MAX (15 + 5) int T, N, W, H; int MAP[MAX][MAX]; int MINANS; void input() { scanf("%d %d %d", &N, &W, &H); for (int r = 0; r 2021. 4. 15. 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 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 15651 : N과 M (3) - 중복 순열 permutation with repetition 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15651 중복으로 숫자를 선택 가능하고, 순서도 의미가 있는 중복 순열 문제이다. 즉, visit배열로 숫자를 현재 선택했는지 관리할 필요가 없다. 따라서 다음 Level에서도 모든 숫자를 선택할 수 있도록 i = 1 ~ N으로 하면 된다. #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) { if (L == M) { outputList(); return; } for (int i = 1; i 2021. 2. 21. BOJ 15649 : N과 M (1) - 순열 permutation 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15649 순열을 구하는 문제이다. 서로 다른 N개중에 M을 선택하는 경우의 수를 의미하고 순서가 상관이 있다. 그리고 중복이 없어야 한다. N = M이면 팩토리얼이 된다. (서로 다른 N개를 모두 나열하는 경우의 수) 예제 입력 2를 예로 4개 중 2개를 선택해서 줄을 세운다면, 아래의 출력이 나온다. 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3 순서에 의미가 있으므로 1 2 와 2 1이 다르다. 경우의 수 문제는 대부분 재귀 호출로 해결한다. 먼저 첫번째를 선택하면 다음 재귀에서는 선택하지 못하도록 해야한다. 따라서 숫자들이 현재 선택된 상태인지 확인하는 배열 visit이 필요하다. 그리고 최.. 2021. 2. 20. 이전 1 다음 반응형
