소프티어

틀린 이유, 위상정렬 사용 안하고 푸는 방법

#include<iostream> #include <map> #include <vector> using namespace std; int main(int argc, char** argv) { int N, K; cin >> N >> K; int *ri = new int[N+1]; int *xi = new int[N+1]; int *res = new int[N+1]; // 초기화 for(int i = 0; i <= N; i++) { res[i] = 0; xi[i] = 1; } map<int, vector<int>> rb; for(int i = 1; i <= N; i++) { int r; cin >> r; // 자식 수 입력 ri[i] = r; vector<int> p; for(int j = 0; j < r; j++) { int tmp; cin >> tmp; p.push_back(tmp); } rb[i] = p; } for(int i = 0; i < K; i++) { res[1]++...

로드 밸런서 트래픽 예측 C++ 반례부탁드립니다.

#include <iostream> #include <vector> #include <queue> #define MAX_SIZE 100004 using namespace std; struct Node{ long long tN; vector<long long> v; }; long long N,K; Node LB[MAX_SIZE]; long long ret[MAX_SIZE]; long long in_degree[MAX_SIZE]; queue<long long> q; void display_() { for(long long i=1;i<=N;i++) { cout << ret[i] << " "; } cout << '\n'; } void check_(long long idx) { bool check_Flag=false; if(LB[idx].tN<ret[idx]) { check_Flag=true; } for(long long i=0;i<LB[idx].tN;i++) { if(check_Fla...

로드 밸런서 트래픽 예측 문제 반례 부탁드립니다..(Topological Sort 사용 X)

import java.util.*; import java.io.*; class Node{ int r; int[] children; long cnt = 0; public Node(int r,int[] children){ this.r = r; this.children = children; } } public class Main { static Node[] nodes; public static void main(String args[]) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N =...

[21년 재직자 대회 예선] 로드 밸런서 트래픽 예측 문제 이해

로드 밸런서 문제를 풀고있는데 문제 이해가 잘 되지 않아서 글을 씁니다. 잘 이해했는지도 햇갈리는데 아래의 문장에서 이해가 안되는 부분이 있어서 도움을 받고자 합니다. 우선 정리하면서 이해한 내용은 아래와 같습니다. i : 서버에 부여된 임의의 고유 숫자 ri : i번째 서버에서 트래픽을 전달할 수 있는 다른 서버 수 xi : i번째 서버가 트래픽을 전달할 때, 어떤 서버로 전달할지 정하는 변수 '(xi mod ri)+1'는 연결된 순서대로 전달한다는 의미 pi,j : i번째 서버에서 (순서상) j번째로 트래픽을 전달할 서버의 고유 숫자 이해가 안되는 문장은 아래와 같습니다. 1. `i → pi, j 간선들로 구성된 그래프에서 사이클이 존재하지 않는다.` 서버 i(i)에서 서버 i와 연결된 j번째 서버(pi,j)로 연결된 간선..은 하나 아닌가요? 왜 간선들일까요? 이해 잘못한것 같은데 흙흙.. 2. `다음 N개의 줄에 ri, pi, 1, pi, 2, ... , pi, rj가 ...

반례 부탁드립니다! [21년 재직자 대회 예선] 로드 밸런서 트래픽 예측

#include #include using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */ struct node{ vector sub; int r; int result; int pos; }; int main(int argc, char** argv) { int N,K,r,p,j,next_node_num; struct node* arr; std::cin>>N; std::cin>>K; arr = new node[N]; //노드 구조 for(int i=0;i>r; arr[i].r = r; arr[i].result = 0; arr[i].pos = 0; for(int j=0;j>p; arr[i].sub.push_back(p)...

[21년 재직자 대회 예선] 로드 밸런서 트래픽 예측 --- 이해가 안되는 현상...

풀이 방법은 각 밸런스 노드에 축적되는 값들을 계산한뒤 분배하는 식으로 카운트를 하는 방식입니다. 이때 특정 밸런스 노드의 parent 가 되는 밸런스 노드 들에서 분배가 끝나도록 했습니다. 밑의 코드는 정답이 출력되는데요, if curr not in set_conquered: 부분이 없으면 오답이 나오게 됩니다. 이부분이 조금 이해가 안되는데요, parent 밸런스 노드들이 모두 분배가 끝났을때 queue 에 현재 밸런스 노드를 추가하기때문에 해당 노드의 방문 횟수는 1번이라고 생각했는데요, 위의 if 문이 없으면 오답 & 시간초과가 나는걸로 봐서 2번이상 방문을 하는것 같습니다. 해당 이유에 대해서 설명해주실수 있는 분이 계실까요?? import sys N, K = [int(el) for el in sys.stdin.readline().split()] list_node = [] for _ in range(N): row = [int(el) for el i...