그린푸딩

다익스트라 시간복잡도 : ElogV (연결된 정점 탐색 x 가장가까운 지점 정렬) 다익스트라 주의점: 음의 가중치가 있을때 무한 사이클이 생길수 있음#include#include#include#define INF 100000000using namespace std; typedef pair ci; vector dijkstra(vector>&graph, vector&dist,int start) { priority_queue, greater>pq; dist[start] = 0; pq.push({ 0,start }); while (!pq.empty()) { int w = pq.top().first; int e = pq.top().second; pq.pop(); if (dist[e] (w + nw)..

어렵다.... 각 파티의 참석인원을 모두 체크해서 무리를 짓고 진실이어야만 하는 무리 체크 후 파티에서 한명만 뽑아서 그 친구의 루트 노드가 진실인지를 판별하면된다. 진실인지를 parent로 한번에 구현할수 있나? 고민하다 꼬여버리고 되는지는 잘 모르겠다. 어렵다.. #include #include #include using namespace std; vectorparent; vectortruth; int find(int node){ if(parent[node]>m; cin>>t; parent.assign(n+1,-1); truth.assign(n+1,0); for(int i=0;i>p; truth[p]=1; //진실 아는사람 } /* if(p==0){ coutnum; cin>>q; int first=q..

29% 틀렸습니다 왜 안되는거야... #include #include #include using namespace std; vectorparent; int find(int node){ if(parent[node]>m>>k; vectorarr; arr.assign(n+1,0); parent.assign(n+1,-1); for(int i=1;i>arr[i]; } int v,w; for(int i=0;i>v>>w; unions(v,w); } //값이 더작은것을 택하기 mapM; long long k1=0; for(int i=1;ik){ cout>w; unions(v,w); } //값이 더작은것을 택하기 long long k1=0; for(int i=1;i

https://www.acmicpc.net/problem/20302 20302번: 민트 초코 상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다. www.acmicpc.net 틀렸습니다 int 값만 빼면 정수인지 판별되지 않을까? 했는데 통과 안됨 왜일까 #include #include using namespace std; int main() { int n; cin>>n; float p; char c; cin>>p; float sum=p; for(int i=0;i>c>>p; if(c=='*'){ sum*=(double)p; } if(c=='/'){ sum/=(double)p; } } if((abs(sum)-(int)abs(sum))>0)..

https://www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net dfs로 탐색하면 어떨까 했는데 재귀로 1000*1000 =1000000정점을 탐색하는것을 시간/공간 복잡도 오류없이 해결할수 있을까 싶어서 dp로 풀었다. dfs,bfs 에 대한 시간/공간복잡도를 따로 정리해봐야겠다.. 접근 방식 1. 맨처음 행으로 진입, 맨끝행에서 달로 갈때도 방향을 계산해야 하나 했는데 첫행은 값 자체를, 끝 행에 도착하면 모든 계산이..

오답 - 1%에서 틀렸습니다 접근1. 1) 지금 위치 다음이 더 높이가 높으면 채울수 있다 가정 (arr[i]) 2) 지금 위치 기준 왼쪽에서 제일 높은 위치의 높이와 비교해서 더 작은 높이로 arr[max_idx]=max_h 3) (지금 위치에서 제일 높은 위치) x ( min(arr[i],arr[max_idx])-arr[i]) 를 곱해주고, 4) arr[i+1]와 비교하여 max_ h와 max_idx를 갱신해준다. 문제점: - 지금 위치 기준 왼쪽으로 칸을 더할때 칸의 높이가 다 다르므로 3)에서 min(arr[i],arr[max_idx])-arr[i] 이부분 고쳐야함 - 지금 위치보다 바로 다음이 더 큰걸 만날때 한번에 왼쪽을 채우고 넘어가려고 max_idx,max_h를 arr[i+1]과 비교해서 ..