본문 바로가기

전체 글

 (90)
2024-03-29 TOPOLOGICAL SORTING 문제들 모아서 풀기 -선수 과목 (14567, 백준) 기본적인 위상정렬 문제이다. ans[x] = x과목을 이수할 수 있는 최소 학기로 두고 진입차수를 감소시킬 때마다 ans를 갱신해주어가며 풀었다. 그냥 DP로도 풀린다고한다. 더보기 #include #include #include #include using namespace std; int n, m; vector vec[1010]; int ent[1010], ans[1010]; int main() { int i, j; scanf("%d %d", &n, &m); for (i = 0; i < m; i++) { int x, y; scanf("%d %d", &x, &y); vec[x].push_back(y); ent[y]+..
2024-03-27 -왕위 계승(5021, 백준) 왕위를 계승하기 위해 초대 왕과 피가 얼마나 섞여있는지 구하면 되는 문제이다. 주어진 유향그래프를 보고 사이클이 없기 때문에 위상정렬을 하는 문제임을 알수있다. 자식노드 = (부모노드1 + 부모노드2) / 2 로 결정되며, 모두 계산후, 주어지는 m명의 사람중 가장 값이 높은 사람을 출력해주면 된다. 더보기 #include #include #include #include #include #include #include using namespace std; int n, m; string king; map vec; map ans; map ent; set st; vector s; int main() { int i, j; cin >> n >> m; cin >> king; ans.i..
2024-03-23 -초콜릿 자르기(2163, 백준) 몇번 직접 그리다보면 규칙을 찾을 수 있다. 항상 N*M의 초콜릿을 1*1로 잘라야 한다. 이때 필요한 초콜릿 조각의 수는 N*M개이고, 한번 자를때마다 초콜릿의 조각은 항상 1개씩 늘어나게 됨으로, 답은 N*M-1개가 된다. 입력되는 수의 범위가 큼으로 자료형에 주의하자. 더보기 #include int main() { long long i, j, n, m; scanf("%lld %lld", &n, &m); printf("%lld", (m * n)-1); return 0; } -서울에서 경산까지(14863, 백준) queue를 이용해 최단경로 구하는 것 처럼 접근을 했지만 생각해보니 Dp를 어렵게 푼것에 불과했다. Dis[현재노드][현재까지 걸린 시간] 일때의 최대 모금..
2024-03-21 -줄서기(14864, 백준) 먼저 1~N까지의 ans배열을 각각의 idx값으로 잡아준다. 그 뒤, 문제에서 입력받는 두 쌍에서 앞쪽 수는 - 뒤쪽수는 +를 시켜준다. 만약 겹치는 수가있거나, 문제에서 주어진 순서와 구해진 순서가 달라지면 -1출력. 아니라면 ans배열을 출력해 준다. 더보기 #include #include #include using namespace std; int n, m; int ans[100010]; bool check[100010]; vector vec; int main() { int i, j; scanf("%d %d", &n, &m); for(i=1;i
2024-03-20 -가운데를 말해요(1655, 백준) 우선순위 큐를 이용한 아이디어성 문제라고 생각한다. mid를 기준으로한 우선순위 큐 두개를 잡아 준 뒤, mid를 기준으로 mid보다 작은 수는 minq에, 큰 수 는 maxq에 넣어준 뒤, minq는 가장 높은수가 위에, maxq는 가장 낮은수가 위에 오게끔해서, 만약 계산후, mid값이 바뀌어야 한다면 균형이 맞게 바꾸어준다. 더보기 #include #include #include using namespace std; int main() { int i, j; int n, mid; priority_queue low, high; scanf("%d %d", &n, &mid); printf("%d\n", mid); for(i=2;i mid) high.push(-x); el..
2024-03-19 -택배 배송(5972, 백준) 간단한 다익 문제이다. 입력받은뒤 1번에서부터 n번노드까지 다익을 돌리면 된다. 더보기 #include #include #include #include using namespace std; int n, m; vector vec[50010]; int dis[50010]; void Dijkstra(int s) { priority_queue pq; pq.push({ 0, s }); dis[s] = 0; while (!pq.empty()) { int nidx = pq.top().second, nval = -pq.top().first; pq.pop(); if (dis[nidx] < nval) continue; for (int i = 0; i < vec[nidx].size(); i++..
2024-03-18 -외판원 순회 2(10971, 백준) TSP기본 문제이다. O(N!)블포로도 풀리지만 나는 비트필드를 이용한 DP를 이용하여 풀었다. 더보기 #include #include using namespace std; int n; int arr[15][15], dp[1
2024-03-17 -백도어(17396, 백준) 다익 기본문제이다. 시아가 있는곳은 넥서스를 제외하고 모두 제외하고 탐색하면 된다. 범위가 매우 크기때문에 자료형을 주의해야한다. 더보기 #include #include #include #include using namespace std; long long n, m; long long ward[100010]; long long dis[100010]; vector vec[100010]; void Dijkstra(long long s) { long long i, j; priority_queue pq; dis[s] = 0; pq.push({ 0, s }); while (!pq.empty()) { long long nidx = pq.top().second, nval = -pq.top..

티스토리툴바