문제풀이
-
BOJ 9663 : N-Queen백준 문제풀이/etc 2020. 5. 19. 12:50
문제 문제 풀어보기 풀이 퀸을 먼저 배치하고 가능한 경우인지 판단하는 알고리즘을 하면 시간 초과로 문제를 풀 수 없었습니다. 그래서 다른 분의 블로그를 참조해서 백트래킹을 사용했습니다. 간단히 설명하자면 퀸을 하나 넣고 퀸의 이동반경을 모두 덱에 넣습니다. 퀸이 들어갈수 있는 곳에 넣으면서 계속 덱에 넣다 보면 퀸의 수가 N 개 이면서 덱의 사이즈가 N * N 이 되는 경우가 생깁니다. 바로 이경우가 퀸을 N 개 위치시킨 경우가 됩니다. 코드 #include #include #include #define safe(x,y) x>=0&&x=0&&y < n using namespace std; int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,-1,..
-
BOJ 13023 : ABCDE백준 문제풀이/GRAPH 2020. 5. 15. 17:59
문제 문제 풀어보기 풀이 문제를 이해하는데 좀 오래 걸렸네요... 이 문제는 A -> B -> C -> D 처럼 친구의 친구의 꼬리를 4번 무는 경우를 찾는 겁니다. 그래서 DFS 를 사용해서 깊이가 4가 되는 경우를 찾으면 됩니다. 코드 #include #include #define max 2000 using namespace std; bool check[max + 1]; vector v[max + 1]; // max+1 개의 벡터 생성 int n, m; void dfs(int st, int index) { check[st] = true; // 깊이가 4인경우 종료 if (index == 4) { cout n >> m; for (int i = 0; i >..
-
BOJ 17140 : 이차원 배열과 연산백준 문제풀이/etc 2020. 5. 10. 22:17
문제 문제 풀어보기 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 저는 R 연산을 구현하고 C 연산에 복붙하고 행과 열만 바꿔서 풀었습니다. 처음엔 계산된 값을 어떻게 삽입을 할지 고민을 많이 했는데, 그냥 하드코딩으로 집어 넣어줘도 시간은 초과되지 않았습니다. 코드 #include #include #include #include #include #include using namespace std; int n = 3; int m = 3; vector arr(105, vect..
-
BOJ 17142 : 연구소 3백준 문제풀이/GRAPH 2020. 5. 10. 21:39
문제 문제 풀어보기 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 간단하게 설명하면 모든 경우에 대해서 BFS를 전부 돌려봐야 하는 문제입니다. 어떤 바이러스를 활성화할 것인지를 고르는 방법이 포인트인데, 조합을 써도 되고 방법은 여러가지 입니다. 저는 비트 마스크를 사용해서 풀었으니 참고하시면 좋을 것 같습니다. 코드 #include #include #include #include #include #include using namespace std; int dx[] = { 1,-1,0,0 }; int dy[] ..
-
BOJ 15686 : 치킨 배달백준 문제풀이/BRUTE FORCE 2020. 3. 1. 16:43
문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 예를 들어, 아래와 같은 지..
-
BOJ 2143 : 두 배열의 합백준 문제풀이/BRUTE FORCE 2020. 2. 12. 22:35
문제 한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오. 예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다. 입력 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000..
-
[재귀] BOJ 9095 : 1, 2, 3 더하기백준 문제풀이/etc 2019. 10. 14. 00:50
문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 풀이 요즘 재귀 함수를 구현하는 법을 많이 연습 중입니다. 브루트 포스 문제들을 해결할 때 재귀 함수가 많은 도움이 되기 때문입니다. 이 문제는 재귀를 처음 접할 때 좋을 것..
-
[ETC] BOJ 13458 : 시험 감독백준 문제풀이/etc 2019. 10. 1. 23:47
문제 총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다. 감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 방에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 방에서 감시할 수 있는 응시자의 수가 C명이다. 각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다. 각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ ..