반응형 dfs48 BOJ 15683 : 감시 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/15683 먼저 모든 카메라가 방향을 가르키게 하기 위해, input에서 camera의 좌표를 따로 저장해두자. 그리고, 5번 카메라의 경우는 방향이 없으므로 따로 모은다. MAP의 경우는 모두 6으로 만든 후, (1, 1)부터 MAP을 만들자. 주변을 미리 벽으로 만들면, 경계 조건을 체크하지 않아도 되기 때문이다. void input() { scanf("%d %d", &N, &M); for (int r = 0; r 2021. 2. 24. 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. 이전 1 2 3 4 5 6 다음 반응형
