[17241] Pineapple Advertising, c++

​

[17241] Pineapple Advertising

 

https://www.acmicpc.net/problem/17241

17241번: Pineapple Advertising

한줄 후기 : 지금 다시 풀면 못풀듯 ? ㅋㅋ

---

이거 존나 빡치는 문제 ㅋㅋ

약간 나 백준에서 사람들이 많이 안 푼 문제 풀고 싶어서 난이도 골드인데도 도전했다가 뼈맞은 그런 거임

암튼..

친절하게 힌트도 있네요 ^^

친절하게 힌트도 있네요 ^^

무튼 처음에 문제 읽고 엥 이거 그냥 그래프 문제 아닌가 ? 하고 바로 코드를 짰슴다 ㅋ

//시간초과
#include <iostream>
#include <vector>
using namespace std;
vector<int> house[200001];
bool check[200001]={false};
int n,m;
int delivery(int a){
	int cnt=0;
	for(int i=0; i<house[a].size(); i++){
		int num = house[a][i];
		if(!check[num]){
			check[num] = true;
			cnt++;
		}
	}
	return cnt;
}
int main(){
	int q,idx=0;
	int count[200000];
	scanf("%d %d %d", &n, &m, &q);
	for(int i=0; i<m; i++){
		int a,b;
		scanf("%d %d", &a, &b);
		house[a].push_back(b);
		house[b].push_back(a);
	}
	for(int i=0; i<q; i++){
		int temp;
		int ans = 0;
		scanf("%d", &temp);
		ans += delivery(temp);
		if(!check[temp]){
			check[temp] = true;
			count[idx++] = ans+1;
			//printf("%d\n", ans+1);
		}
		else{
			count[idx++] = ans;
			//printf("%d", ans);
		}
	}
	for(int i=0; i<q; i++){
		printf("%d\n", count[i]);
	}
	return 0;
}

결과는 시간초과 ..

무난한 그래프 문제 처럼 vector 에 house 연결을 받아 놓고 delivery 함수를 통해 돌면서 피자를 나눠 주는 걸 체크했더니 시간초과가 납니다.

저는 이걸 풀지 못했어요 ..~ 그래서 unsolved 로 냈답니다.

wow 그랬더니 한 선배님께서 친절히 알려주셨어요 .. delivery 를 그냥 도는게 아니라 check 배열 내에 이미 피자를 좋아하는 집, 피자를 전달받아서 좋아하게 된 집 을 따로 표시하면 시간을 줄일 수 있다고 ..

그래서 고쳤습니다.

//AC
#include <iostream>
#include <vector>
using namespace std;
vector<int> house[200001];
int visit[200001] = {0};
int delivery(int start){
	int cnt = 0;
	if(visit[start] == -2)	return 0;  //이미 좋아함
	if(visit[start] == 0){
		cnt++;
		visit[start] = -2; 
	}
	for(int i=0; i<house[start].size();i++){
		int a = house[start][i];
		if(visit[a]==0){
			cnt++;
			visit[a] = -1; // 피자 전달된 집이랑 연결된 집
		}
	}
	return cnt;
}
int main(){
	int n,m,q;
	scanf("%d %d %d", &n, &m, &q);
	for(int i=0; i<m; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		house[a].push_back(b);
		house[b].push_back(a);
	}
	for(int i=0; i<q; i++){
		int temp;
		scanf("%d" ,&temp);
		printf("%d\n", delivery(temp));
	}
	return 0;
}

휴.. 어려운 문제였습니다. 골드 문제는 신중히 푸는 거로 ^^