이 문제는 이분탐색 문제이다 처음 그냥 대충 쉽게 접근하다가 틀렸는데 같은수가 여러번 들어갈수 있음을 망각했다
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
long long n;
vector<long long > inputData;
int main() {
cin >> n;
long long tmp;
long long cnt = 0;
for (long long i = 0; i < n; i++) {
cin >> tmp;
inputData.push_back(tmp);
}
sort(inputData.begin(), inputData.end());
for (long long i = 0; i < n; i++) {
long long left = n-1;
long long right = 0;
while (right <n && left>=0 && right<left) {
if (right == i) {
if (right < n-1) {
right += 1;
}
}
if (left == i) {
if (left > 0) {
left -= 1;
}
}
if (left == right) {
break;
}
if ((inputData[right] + inputData[left]) == inputData[i]) {
cnt += 1;
break;
}
else if ((inputData[right] + inputData[left]) > inputData[i]) {
left -= 1;
}
else if ((inputData[right] + inputData[left]) < inputData[i]) {
right += 1;
}
}
}
cout << cnt;
}
전체 코드는 이렇게 된다 처음에는 2/n 기준으로 양옆으로 펼쳐지면서 값을 찾으려 했으나 이렇게 하면 못찾을 때 가 발생해서 양옆에서 조이는 방식으로 진행 했다
해당 게시물을 참조하면 이해가 쉬울 것이다 즉 순서에 맞춰서 나열 하면 되는게 위상 정렬 이다
이 문제에서는 어떠한 노드 가 나로 올수 있는 점입차수 라는것을 들고 있어야 한다 점입차수가 0이면 먼저 뽑아도 무방한 노드라고 보면 된다 즉 우리는 이문제를 풀때 점입차수를 비교해가며 큐에 넣어서 pop 하면 되는 문제이다
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int inCount[100001] = { 0, };
vector<vector<int>> v(n + 1);
for (int i = 0; i < m; i++) {
int tmp1, tmp2;
cin >> tmp1 >> tmp2;
v[tmp1].push_back(tmp2);
inCount[tmp2]++;
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (inCount[i] == 0)
q.push(i);
}
while (!q.empty()) {
cout << q.front() << " ";
int idx = q.front();
for (int i = 0; i < v[idx].size(); i++) {
inCount[v[idx][i]] -= 1;
if (inCount[v[idx][i]]<=0)
q.push(v[idx][i]);
}
q.pop();
}
}
일단 전체 코드는 이렇게 된다 입력 받을 때 어떠한 노드를 입력 받고 이노드가 갈수 있는 노드도 Vector에 넣어 놓느다 그후 연결 된 노드의 점입 차수를 1증가 시킨다 이렇게 입력 을 받은 후 우리는 해당 vector를 순회하면 서 일단 점입차수가 0인걸 queue에다가 넣는다 그후 while문으로 큐를 순회하면서 점입차수가 0인 걸 팝해주면 나와 연결된 노드들의 점입 차수를 1감소시켜준다 그렇게 점입차수가 0인 노드들을 지속적으로 queue에 넣었다 팝해주면 해당 문제는 풀린다
이 문제는 그리디이다 이문제는 얼피하면 그냥 정렬한후 처리처리 하게 하는거로 생각해서 틀릴 수가 있다 이문제의 경우 최소의 해를 그리디로 만족 시키기위해서는 큰 화물을 처리할 수 있는 화물은 최대한 큰것 부터 처리 해야한다는 것이다 백준에서 제공 하는 3번 input을 이용해서 보자
이렇게 테스트 케이스가 주어졌을때 Krane 을 처리 할 수 있는 무게에 따라 오름 차순 정렬해주면 23 25 28 32 이렇게 정렬이 된다 이제 화물을 오름 차순으로 정렬해보자 2 5 7 10 16 18 20 24 27 32 이렇게 정렬이 된다.
이후 3번째 크레인이 처리 할수 있는 최대 무게는 32 임으로 해당 크레인은 일단 32를 처리 한다 2번 째크레인은 27을 처리하고 1번째 크레인은 24를 0번째 크레인은 23을 처리한다 이렇게 처리하면 1초가 지나간다
그 후 크레인은 내가 현재 보고있는 화물이 이미 처리되어있으면 다음 화물을 처리하기 위해서 내가 지금 있는 위치에서 이전 위치까지 탐색하다 화물이 안처리되었으면 처리하면 된다 이렇게 로직이 가능한 이유는 오름차순 정렬을 했기 때문에 내가 처리한 화물 이전에 있는 화물들은 다처리 할 수 있기 때문이다
코드는 아래와 같다
#include<iostream>
#include<algorithm>
using namespace std;
int krane[50];
int cargo[10000];
int kraneidx[50];
bool isDo[10000];
// 각 Krane이 처리할수 있는 최대 무게의 index저장
int clear;
int n, m;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin>>krane[i];
}
cin >> m;
for (int i = 0; i < m; i++) {
cin>>cargo[i];
}
sort(krane, krane + n);
sort(cargo, cargo + m);
if (krane[n - 1] < cargo[m - 1]) {
cout << -1;
return 0;
}
int maxKrane = n - 1;
for (int i = m - 1; i >= 0; i--) {
if (maxKrane < 0)
break;
if (krane[maxKrane] >= cargo[i]) {
kraneidx[maxKrane] = i;
maxKrane--;
}
}
for (int i = 0; i <= maxKrane; i++) {
kraneidx[i] = -1;
}
int cnt = 0;
maxKrane = kraneidx[n - 1];
while (maxKrane > 0) {
maxKrane = kraneidx[n - 1];
for (int i = n - 1; i >= 0; i--) {
if (kraneidx[i] < 0)
continue;
if (!isDo[kraneidx[i]]) {
isDo[kraneidx[i]] = true;
}
else {
while (isDo[kraneidx[i]] && kraneidx[i]>=0) {
kraneidx[i] -= 1;
}
if(kraneidx[i] >= 0)
isDo[kraneidx[i]] = true;
}
}
if (kraneidx[n - 1] < 0)
break;
cnt += 1;
}
cout << cnt;
}
이 문제는 다 풀어놓고 하나를 실수 해서 조금 헤맸었다 이 문제는 일반적인 다익스트라 문제이다 이에 소스코드는 이렇게 되고 25% 에서 이슈가 있었다
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> djikstra_pq;
vector<pair<int, int>> edgeList[100000];
vector<int> distance_v;
int testCase;
int n, d, c;
#define INF 1000000001
void djikstraSolution(int start) {
int startNode = start;
int toCost = 0;
djikstra_pq.push({ toCost,startNode });
while (!djikstra_pq.empty())
{
int vertex = djikstra_pq.top().second;
int toCost = djikstra_pq.top().first;
djikstra_pq.pop();
if (toCost > distance_v[vertex])
continue;
for (int i = 0; i < edgeList[vertex].size(); i++) {
int nextVertex = edgeList[vertex][i].first;
int nextCost = edgeList[vertex][i].second;
if (distance_v[nextVertex] > nextCost + toCost) {
distance_v[nextVertex] = nextCost + toCost;
djikstra_pq.push({ nextCost + toCost,nextVertex });
}
}
}
}
int main() {
cin >> testCase;
for (int i = 0; i < testCase; i++) {
cin >> n >> d >> c;
for (int i = 0; i < d; i++) {
int from, to, cost;
cin >> from >> to >> cost;
edgeList[to].push_back({ from,cost });
}
distance_v.assign(n + 1, INF);
int cpuCnt, lastSecond;
djikstraSolution(c);
lastSecond = 0;
cpuCnt = 0;
distance_v[c] = 0;
for (int i = 1; i <= n; i++) {
if (distance_v[i] != INF) {
cpuCnt++;
if (distance_v[i] > lastSecond) {
lastSecond = distance_v[i];
}
}
edgeList[i].clear();
}
cout << cpuCnt << " " << lastSecond << endl;
}
}
이런식으로 되는데 내가 처음에 distanceVector를 초기화 해줄 때 나에서부터 나까지의 거리는 0이라고 설정을 안해놓았었다 그 후 무조건 감염 PC는 하나니 cpuCnt값을 1로두고 셌다 근데 문제는 여기서 a->b b->a 로가는 경로가 생길시 a의 경로값이 갱신 되면서
if (distance_v[i] != INF) {
cpuCnt++;
이 부분에서 CPUCNT가 하나더 증가해서 이미센 감염피씨를 한번 더세면서 문제가 틀렸었다 이에 감염된 피씨의 초를 0으로 바꿔주고 cpuCNt의 값을 0으로 바꿔주니 정상적으로 나왔다
이 문제는 간단한 문제인줄 알고 건드렸다가 2시간을 날릴 정도로 고생한 문제이다 일단 이 문제의경우 딱 봤을 때 BFS를 사용하는거는 확실 해 보이지만 매번 시추할 때 마다 BFS를 돌리면 효율성 검사에서 점수가 떨어지게 된다 이에 이문제는 BFS를 이용해서 뽑아낸 데이터를 어떤 자료 구조에 넣어 사용하는 지가 매우 중요한 문제이다
#include <string>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
int directionX[4] = { 1, 0, -1, 0 };
int directionY[4] = { 0, 1, 0, -1 };
int isVisited[501][501] = { 0, };
map<int, int> sizeOfOil;
int sizeOfLandX;
int sizeOfLandY;
int areaNum = 1;
vector<vector<int>> oilMap;
void BFS(int startX, int startY ) {
int tmp = 0;
queue<pair<int, int>> q;
q.push({ startX, startY });
oilMap[startX][startY] = areaNum;
isVisited[startX][startY] = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
tmp++;
q.pop();
for (int i = 0; i < 4; i++) {
int nextX = x + directionX[i];
int nextY = y + directionY[i];
if (nextX >= 0 && nextX < sizeOfLandX && nextY >= 0 && nextY < sizeOfLandY && isVisited[nextX][nextY] == false && oilMap[nextX][nextY]>0) {
oilMap[nextX][nextY] = areaNum;
isVisited[nextX][nextY] = 1;
q.push({ nextX,nextY });
}
}
}
sizeOfOil[areaNum] = tmp;
areaNum++;
}
int solution(vector<vector<int>> land) {
int answer = 0;
oilMap = land;
sizeOfLandX = land.size(); //열의 길이
sizeOfLandY = land[0].size(); //행의 길이
for (int i = 0; i < sizeOfLandX; i++) {
for (int j = 0; j < sizeOfLandY; j++) {
if (isVisited[i][j] == false && land[i][j] == 1) {
BFS(i, j);
}
}
}
for (int j = 0; j < sizeOfLandY; j++) {
set<int> oilSet;
int sumOfOil=0;
for (int i = 0; i < sizeOfLandX; i++) {
oilSet.insert(oilMap[i][j]);
}
set<int>::iterator iter;
for (auto it : oilSet) {
sumOfOil += sizeOfOil[it];
}
answer = max(answer, sumOfOil);
}
return answer;
}
일단 이 문제의 경우 내가 블로그에 기존에 올렸던 BFS보다 간단 하다 원래는 Direction을 일일히 내가 정해줬었는데 이를 배열에 넣어 간단하게 보이게 했다. 코드 가독성이 올라가니 확실히 디버깅 효율이 올라갔다
자 일단 이문제의 핵심로직은 BFS로 구해놓은 영역의 유전의 크기를 영역별로 들고 있어야 한다 이를 위해 위 코드에
void BFS(int startX, int startY ) {
int tmp = 0;
queue<pair<int, int>> q;
q.push({ startX, startY });
oilMap[startX][startY] = areaNum;
isVisited[startX][startY] = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
tmp++;
q.pop();
for (int i = 0; i < 4; i++) {
int nextX = x + directionX[i];
int nextY = y + directionY[i];
if (nextX >= 0 && nextX < sizeOfLandX && nextY >= 0 && nextY < sizeOfLandY && isVisited[nextX][nextY] == false && oilMap[nextX][nextY]>0) {
oilMap[nextX][nextY] = areaNum;
isVisited[nextX][nextY] = 1;
q.push({ nextX,nextY });
}
}
}
sizeOfOil[areaNum] = tmp;
areaNum++;
}
BFS 부분에서sizeOfOil에 저장해 주었다 여기서 sizeOfOil은 맵 자료형이다 맵자료형은 map<int,int>이렇게 사용했을 때 맨앞에 오는 값은 Key로서 두번쨰 오는 값은 value로 써 작용합니다. 즉 map<key,value> 의 형태로 각각의 해당하는 자료형을 넣어주면 됩니다 .
이 문제에서는 Map의 저장해놓은 데이터를 순환하여 찾아와야 하기 때문에
for (auto iter = m.begin() ; iter != m.end(); iter++)
{
cout << iter->first << " " << iter->second << endl;
}
cout << endl;
의 형태와
for (auto iter : m) {
cout << iter.first << " " << iter.second << endl;
}
의 형태의 두가지 형태로 map을 순환 할 수 있습니다. 이에 필자는 두번째 형태로 사용하였습니다.
이렇게 Map형태로 저장해놓은 데이터에서 우리는 land 배열에 새로줄에서 만나는 areaNum들을 set에 넣어줍니다. Set은 마찬가지로 중복되는 자료를 넣으면 넣지 않기 때문에 areaNum을 최대 1번씩만 넣을 수 있습니다 이에 set.insert를 이용해서 각 세로줄에 있는 유전의 areaNum을 넣습니다.
그후 이를 순회하면서 areaNum을 통해 세로줄에 있는 해당 유전에 크기를 더하여 최대값을 출력합니다
