๋ฌธ์
9489๋ฒ: ์ฌ์ด
์ ๋ ฅ์ ์ฌ๋ฌ ๊ฐ์ ํ ์คํธ ์ผ์ด์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์๋ ๋ ธ๋์ ์ n๊ณผ ์ฌ์ด์ ์๋ฅผ ๊ตฌํด์ผ ํ๋ ๋ ธ๋์ ๋ฒํธ k๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) ๋ค์ ์ค
www.acmicpc.net
์ฝ๋
#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;
int graph[1000001];
vector<int> idx;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
while(cin>>n>>k){
if(n==0 && k==0) break;
int parent_idx = -1, before = 0, ans = 0;
for(int i=0; i<n; i++){
int inp; cin>>inp;
idx.push_back(inp);
if(i==0){
before = inp;
graph[inp] = inp;
}
else{
if(before+1 == inp){
graph[inp] = idx[parent_idx];
before = inp;
}
else{
before = inp;
graph[inp] = idx[++parent_idx];
}
}
}
for(int node: idx){
if(graph[graph[node]] == graph[graph[k]] && graph[node] != graph[graph[k]] && graph[node]!= graph[k] && graph[k] != graph[idx[0]]) ans++;
}
cout<<ans<<'\n';
idx.clear();
memset(graph,0,sizeof(graph));
}
}
ํ์ด
์ ๋ ฅ์ด ์กฐ๊ธ ๊น๋ค๋กญ๊ฒ ๋ค์ด์์ ์ ๋ ฅ ์ฒ๋ฆฌ์ ๊ฝค ๊ณต์ ๋ค์๋ ๋ฌธ์ ์์ต๋๋ค.
์ ๋ ฅ๋ง ์ฒ๋ฆฌํด์ฃผ๋ฉด ๊ทธ ์ดํ๋ ์ด๋ ต์ง์์ต๋๋ค. ์ฌ์ด ๋ ธ๋๋ ํ์ค์ ๋ป ๊ทธ๋๋ก ๋ถ๋ชจ๋ ๋ค๋ฅด์ง๋ง ๋ถ๋ชจ์ ๋ถ๋ชจ๋ ๊ฐ์ ๋ ธ๋๋ฅผ ๋ปํฉ๋๋ค.
์ ์ด๋ฏธ์ง์์ 15์ ์ฌ์ด ๋ ธ๋๋ค์ ๋ถ๋ชจ์ ๋ถ๋ชจ๊ฐ ๊ฐ์ 8, 9, 30, 31, 32๊ฐ ๋ฉ๋๋ค.
์ฌ๊ธฐ์ ์ฃผ์ํด์ผ ํ ์ฃ์ง์ผ์ด์ค๋ 3, 4, 5์ ๋๋ค. 3, 4, 5 ๋ ธ๋์ ๊ฒฝ์ฐ ์ฌ์ด์ด ์๋๋ผ ์ผ์ด์ด๊ธฐ ๋๋ฌธ์ ์กฐ๊ฑด๋ฌธ์์ ๊ฑธ๋ฌ์ฃผ์ด์ผ ํฉ๋๋ค.
for(int node: idx){
if(graph[graph[node]] == graph[graph[k]] && graph[node] != graph[graph[k]] && graph[node]!= graph[k] && graph[k] != graph[idx[0]]) ans++;
}
์ ๋ ๋ชจ๋ ๋ ธ๋๋ค๋ง๋ค ๋ถ๋ชจ๋ ธ๋๋ฅผ ์ ์ฅํด์ค ๋ค, ์ ์ฝ๋๋ฅผ ํตํด ์ฌ์ด์ธ์ง ํ๋ณํ์ฌ ์ ๋ต์ ๊ตฌํ์ต๋๋ค.
'Algorithm ๐ง๐ปโ๐ป > ๋ฐฑ์ค(BOJ)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค,c++] 13164๋ฒ - ํ๋ณต ์ ์น์ (0) | 2022.07.27 |
---|---|
[๋ฐฑ์ค,c++] 2138๋ฒ - ์ ๊ตฌ์ ์ค์์น (0) | 2022.07.27 |
[๋ฐฑ์ค,c++] 1167๋ฒ - ํธ๋ฆฌ์ ์ง๋ฆ (0) | 2022.07.26 |
[๋ฐฑ์ค,c++] 20924๋ฒ - ํธ๋ฆฌ์ ๊ธฐ๋ฅ๊ณผ ๊ฐ์ง (0) | 2022.07.24 |
[๋ฐฑ์ค,c++] 20365๋ฒ - ๋ธ๋ก๊ทธ2 (0) | 2022.07.24 |
[๋ฐฑ์ค,c++] 12933๋ฒ - ์ค๋ฆฌ (0) | 2022.07.19 |
๋๊ธ