반응형 조합7 BOJ 23290 : 마법사 상어와 복제 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) https://www.acmicpc.net/problem/23290 먼저, 문제 아래에 설명된 상어의 이동 방법에 대해 구현해보자. 상어의 이동 방법은 상하좌우 = 1, 2, 3, 4 중 3개를 선택하는 중복 조합이다 따라서 43 = 64가지 방법을 미리 구현해둔다. N과 M (4) - 중복 조합 코드에서 outputList를 고치면 된다. 상하좌우에 대한 경우의 수는 moveList에 저장해둔다. typedef struct st2 { int move[3]; }MOVE; MOVE moveList[70]; int mcnt; int list[10]; void outputList() { //for (int i .. 2021. 11. 6. BOJ 17471 : 게리맨더링 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17471 A형에서 그래프는 2차원 배열로 만들면 대부분 충분하다. 제시된 N이 매우 작기 때문이다. (N이 매우 큰 그래프는 링크드 리스트를 이용해 그래프를 만들어야 한다.) 만약 1번 구역과 2번 구역이 인접하다면, MAP[1][2] = MAP[2][1] = 1, 그렇지 않다면 0이 된다. people 배열에는 구역의 인구 수를 저장한다. #define MAX (10 + 5) int N; int MAP[MAX][MAX]; int people[MAX]; void input() { scanf("%d", &N); for (int i = 1; i 2021. 4. 28. BOJ 17135 : 캐슬 디펜스 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17135 먼저 궁수가 탐색해야할 우선순위를 구해보자. 아래의 그림은 D = 1, 2, 3인 경우 궁수가 탐색해야하는 순서다. 적이 가장 가까울 경우 가장 왼쪽에 있는 적을 공격한다고 하였으므로, 거리가 가장 가까운 앞을 보고, 그 다음 거리부터는 왼쪽/가운데/오른쪽 순서대로 탐색한다. D = 4인 경우, 규칙이 점점 보인다. 위의 탐색 순서를 궁수를 기준으로 r, c로 나타내면 아래와 같다. 좌표 r은 -1부터 시작해서 감소하다가 다시 증가한다. 좌표 c는 처음엔 0이며, 그 다음 주기에는 -1 부터 1씩 증가, 그 다음은 -2부터 1씩 증가한다. 이 주기.. 2021. 4. 11. 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 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 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. BOJ 15650 : N과 M (2) - 조합 combination 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15650 N과 M(1) - 순열이 줄 세우기 문제라면, 이번 문제는 조합문제이다. 1 2 3 4 = 1 2 4 3 = ... = 4 3 2 1 이 모두 중복으로 취급된다. 즉, 순서가 상관이 없다. 그리고 사전 순으로 증가하도록 출력해야하므로, DFS Level에서 start를 기억해두고, start에서 N까지만 list를 작성하도록 만들면 된다. list에서 선택한 번호를 저장하고, 선택한 번호 + 1을 다음 DFS에 넘겨주면 된다. 이렇게 되면, 선택한 번호는 다음 DFS Level에서 선택할 수 없으므로, visit 배열이 필요가 없다. #include int N, M; int list[10]; void outputList() {.. 2021. 2. 20. 이전 1 다음 반응형
