๋ฌธ์
14267๋ฒ: ํ์ฌ ๋ฌธํ 1
์์ ํ์ฌ์๋ ๋งค์ฐ ์ข์ ๋ฌธํ๊ฐ ์๋๋ฐ, ๋ฐ๋ก ์์ฌ๊ฐ ์ง์ ๋ถํ๋ฅผ ์นญ์ฐฌํ๋ฉด ๊ทธ ๋ถํ๊ฐ ๋ถํ์ ์ง์ ๋ถํ๋ฅผ ์ฐ์์ ์ผ๋ก ์นญ์ฐฌํ๋ ๋ด๋ฆฌ ์นญ์ฐฌ์ด ์๋ค. ์ฆ, ์์ฌ๊ฐ ํ ์ง์ ๋ถํ๋ฅผ ์นญ์ฐฌํ๋ฉด ๊ทธ ๋ถํ
www.acmicpc.net
์ฝ๋
#include <iostream>
#include <vector>
using namespace std;
vector<int>graph[100001];
int point[100001];
void add_point(int node, int _point){
point[node] += _point;
for(auto next: graph[node]){
add_point(next, point[node]);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m; cin>>n>>m;
for(int i=1; i<=n; i++){
int inp; cin>>inp;
if(inp==-1) continue;
graph[inp].push_back(i);
}
for(int i=0; i<m; i++){
int peo, cost; cin>>peo>>cost;
point[peo] += cost; // peo: ์ง์๋ฒํธ, cost: ์นญ์ฐฌ์ ๋
}
add_point(1, point[1]);
for(int i=1; i<=n; i++){
cout<<point[i]<<' ';
}
}
ํ์ด
์์ ์ด ์นญ์ฐฌ๋ฐ์ผ๋ฉด ์์ ๋ณด๋ค ์๋ ์ง์๋ฅผ ๊ฐ์ง ๋ชจ๋ ์ง์์ ์นญ์ฐฌ ์ ์ ๋ํ ์ฆ๊ฐ์ํค๋ ๋ฌธ์ ์ ๋๋ค.
๋ฏธ๋ฆฌ ์ง์๋ค์ด ์นญ์ฐฌ๋ฐ์ ์ ๋๋ฅผ ์ ๋ ฅ๋ฐ๊ณ , dfs๋ฅผ ํ ๋ฒ๋ง ๋๋ฆฌ๋ฉด ํด๊ฒฐํ ์ ์์ต๋๋ค. ๋ง์ฝ ๋ฏธ๋ฆฌ ์ง์๋ค์ด ๋ฐ์ ์นญ์ฐฌ ์ ๋๋ฅผ ์ ๋ ฅ๋ฐ์ง ์๊ณ ์ ๋ ฅ๋ฐ์ ๋๋ง๋ค dfs๋ฅผ ๋๋ ค ์ ์๋ฅผ ๋ํด์ค๋ค๋ฉด ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ๊ฒ ๋ฉ๋๋ค.
- ์นญ์ฐฌ๋ฐ์ ์ ๋๋ฅผ ๋จผ์ ์ ์ฅํ๋ค.
- dfs๋ฅผ 1๋ฒ ์ง์์ ์์์ ์ผ๋ก ์ํํ๋๋ฐ, ๋ณธ์ธ์ด ๋ฐ์ ์นญ์ฐฌ ์ ์๋ฅผ ๋ํ๋ค.
- ๋ณธ์ธ ์๋์ ์ง์๋ค์ dfs๋ฅผ ๋๋ฆฌ๋๋ฐ, ์๋์ ์ง์์ ๋ณธ์ธ ์์ฌ๊ฐ ๋ฐ์ ์ ์๋ฅผ ๋ํ๋ค.
'Algorithm ๐ง๐ปโ๐ป > ๋ฐฑ์ค(BOJ)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค,c++] 11437๋ฒ - LCA (0) | 2022.08.17 |
---|---|
[๋ฐฑ์ค,c++] 15900๋ฒ - ๋๋ฌด ํ์ถ (0) | 2022.08.15 |
[๋ฐฑ์ค,c++] 1595๋ฒ - ๋ถ์ชฝ๋๋ผ์ ๋๋ก (0) | 2022.08.15 |
[๋ฐฑ์ค,c++] 19542๋ฒ - ์ ๋จ์ง ๋๋ฆฌ๊ธฐ (0) | 2022.08.14 |
[๋ฐฑ์ค,c++] 2250๋ฒ - ํธ๋ฆฌ์ ๋์ด์ ๋๋น (0) | 2022.08.14 |
[๋ฐฑ์ค,c++] 19637๋ฒ - IF๋ฌธ ์ข ๋์ ์จ์ค (0) | 2022.08.02 |
๋๊ธ