홍시홍의 프로그래밍

요구사항 n*n이 주어졌을대 n번째 큰 수를 구하라 풀이 메모리 제한이 12MB이므로 [1500][1500]배열도 선언할 수 없고, vector의 크기도 1500*1500가 될 수 없다 단순히 우선 순위 큐의 크기를 n만큼으로 제한하여서 문제를 해결할 수 있다. n개의 최소 힙을 선언하여 n개의 최소보다 더 크다면 pop한 후, 다시 넣을 수 있도록 한다 #include #include #include #include #include using namespace std; priority_queue q; int n; vector v; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int x; ..

요구사항 1. 주유소에 최소한의 횟수만 들려서 마을에 도착하기 풀이 주어지는 입력 L과 P를 주유소-마을까지의 거리 L 내가 이미 간 거리 P 라고 생각하면 쉽게 풀 수 있는 문제 인듯 한다. 1. 이미 dist만큼 이동 한 후, dist까지 이동하면서 들릴 수 있는 주유소의 기름 양을 우선 순위 큐에 넣어 준다. 2. 제일 많은 기름을 가지고 있는 기름 양 만큼 넣어준다(cnt++) 3. 다시 1번 과정을 반복한다 dist가 goal 만큼 왔을때 or 큐가 비었을때 멈춰서 정답을 출력한다 뭔가 두번 꼬아져 있는 문제인거 같다 #include #include #include #include using namespace std; struct go { int x; int y; }; int n; go map[..

요구사항 1. 최대한 단어를 많이 알기 위한, 단어 K개 선택 2. 최대한 많이 아는 단어 출력 풀이 1. anta, tica는 알아야지 단어를 알 수 있다. 그러므로 최소 a n t a c 는 알아야지 단어를 알 수 있다.(k b.cnt) return true; return false; } int alpha[50]; int n, k; char input[50][20]; int ans = 0; void dfs(int cnt, int now) { if (cnt + 5 == k) { int flag = 0; int count = 0; for (int i = 0; i < n; i++) { flag = 0; for (int j = 0; input[i][j] != 0; j++) { int now = (int)in..

요구사항 1. bfs를 이용하여 성곽의 최대 크기와 성의 갯수 구하기 2. 성곽을 1개 허물었을때 최대 크기 구하기 풀이 동서남북이 열려져 있는가 확인 하기 위해서 map[i][j] & (1