https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 이 문제는 입력의 범위가 좀 크기 때문에 그냥 O(N^2)으로 탐색하게 되면 시간초과가 발생할 수 있는 가능성이 존재한다. 그러면 어떻게 푸냐? 그리디 알고리즘을 이용하자! 1. 우선 입력을 받고, 2. 보석의 정보와 가방의 정보들을 오름차순(작은 것부터)으로 정렬해준다. 정렬할 때는 greater나 less를 사용해도 되지만, 비교..
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si pq; int n,s,t; /*bool compare(pair a, pair b){ if(a.first > n; for(int i=0;i> s >> t..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 구현 + bfs 문제라서 조금 까다로웠다. 보통 구현, 시뮬레이션 이쪽 문제들은 꼼꼼히 읽고 자잘하게 챙겨줘야하는 것들이 많으니 유의하시길 바란다! 우선, 원소 하나하나에 대해 bfs를 해준다. bfs에 들어가기 전에 연합 정보를 저장할 벡터를 이용해 벡터에 탐색을 '시작하는' 곳의 좌표를 넣어주고, 연합의 인구 수를 계산할 변수인 sum에 현재 나라의 인구 수를 저장해준다. bfs..
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 골드4티어 문제치고는 좀 쉽다는 생각이 들었다. 요즘 빡센 bfs 구현문제만 풀어서 그런가..? 싶지만 자만하지 말자.. 우선순위 큐를 하나 선언하는데, 기본 값은 내림차순(큰 값이 우선) 이므로 오름차순으로 정렬되도록 선언해준다! 그리고 제일 작은 것과 그 다음 작은 것 2개를 가져와서 더한 후, 다시 큐에 넣는다. 이 때 정답은 누적합으로 구해준다. 큐가 비거나 하나밖에 없다..
https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 우선 입력을 받고, 빨간 구슬의 위치와 파란 구슬의 위치를 구조체를 하나 만들어서 동시에 관리해준다. 큐에 담겨있는 정보를 가져와 4방향에 대해 탐색을 하는데, 벽을 만나거나 탐색한 곳이 구멍이 아닐 때까지 while문을 통해서 쭈욱 직진한다. (이 개념이 이해가 되지 않는다면 백준 레이저 통신 문제를 풀어보시길..!) 판을 한 방향으로 기울여 볼..
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 1. 입력받을 때, 9가 나오면 상어의 위치이므로 기록해둔다. 2. 다른 물고기들의 개수를 세서 물고기가 오직 한마리면 바로 거리를 계산하고 종료! -> (x좌표의 차 + y좌표의 차) = 거리 3. 만약 물고기가 여러 마리일 경우, bfs()를 반복실행! ※ 반복실행하는 이유 : 상어가 가장 가까운 먹이를 찾아서 그것을 먹을 때 마다, 다른 먹이들과의 최단거리가 바뀌기 때문에 다시 게산..
