이것 저것 &

문제링크:https://www.acmicpc.net/problem/5567

구현문제입니다.

문제가 직관적이기 때문에 구현에 어려움은 없으실겁니다.

제가 고민했던 문제는 실행시간입니다.

m<= 10000 이기때문에  m을 입력받고 O(m*m)인 이중포문으로 구현하게 되면 O(100,000,000)으로 1억번 실행되기에 1초에 딱맞습니다. 그래서 시간초과가 날까 걱정했습니다.

#include <iostream>
using namespace std;
int n = 0, m = 0, result = 0;
bool visited[501] = { 0 };
int arr[10000][2] = { 0 };
int main() {
	cin >> n >> m;

	for (int i = 0; i < m; i++) 
		cin >> arr[i][0] >> arr[i][1];

	for (int i = 0; i < m; i++) {
		if (arr[i][0] == 1) { //상근이의 친구
			int val = arr[i][1];
			visited[val] = 1; //체크
			for (int j = 0; j < m; j++) {// 상근이 친구의 친구들도 체크
				if (arr[j][0] == val)
					visited[arr[j][1]] = 1;
				else if (arr[j][1] == val)
					visited[arr[j][0]] = 1;
			}
		}
	}

	for (int i = 1; i <= n; i++)
		if (visited[i] == 1) {
			result++;
			
		}
	cout << result - 1 << endl;
}

다행히 ac를 받았습니다.

시간도 얼마걸리지 않았습니다. ( 아마 테스트케이스에 극단값이 없을 수 있기 때문에 )

구현문제는 항상 좀더 컴팩트한 답을 생각하셔야 합니다.

#include <cstdio>
int main(){
    int n,m,a,b,ans=0;
    short int arr[501][501]={0,};
    scanf("%d%d",&n,&m);
    for(int i =0 ; i<m; i++)
        scanf("%d%d",&a,&b),arr[a][b] = 1,arr[b][a] = 1;
    for(int i=2; i<=n; i++){
        if(arr[1][i] ==1){
            ans++;
        }
        else{
            for(int j = 1; j<=n; j++){
                if(arr[i][j] == 1 && arr[j][1] == 1){
                    ans++;break;
                }}}}
    printf("%d\n",ans);
}

위 처럼 그래프에 값들을 저장하고 O(n*n)으로 계산할 수 있었습니다.

실행시간도 훨씬 적고 정작 배열의 크기도 작아 메모리도 더 적게 드는 답안이었습니다.

화이팅 :)