백준 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 C언어_230110

한윤정 씨가 이탈리아에 갔다. 부들부들

문제를 풀면서 항상 수학과 국어 총제적 난국을 겪고 있는데 이문제도 그러하였다.

 

우선 문제를 살펴보면 중복 없이!! 먹을 수 있는 조합을 찾는 문제이다.

처음에 문제가 이해가 안 가서 일단 엑셀에 표시하면서 먹을 수 있는 조합을 찾다가 이차원배열로 문제를 풀어야겠다고 생각이 들었다.

na	x	x
x	na
x		na	x
		x	na
				na

내가 생각하는 문제의 핵심은 아래 2가지로 이 부분을 고려하여 코딩하기 위해 코드를 짰다.

물론 더 좋은 방법이 있을 것이다.

 

1. 세 숫자가 모두 1로 flag 되어있는 경우 제외할 것

2. 각 경우를 담을 수 있는 배열을 만들 것

#include <stdio.h>

int main(){
	int n,m,a,b;
	int check[300][300]={0};
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d %d",&a,&b);
		check[a][b]=1; //먹을 수 없는 조합일 경우 1 대입
		check[b][a]=1;
	}
	int cnt=0;
	for(int i=1;i<=n;i++){ //조합 3개를 만들기 위해 3중 루프를 돌렸다.
		for(int j=i+1;j<=n;j++){
			for(int k=j+1;k<=n;k++){
				if(i!=j &&j!=k&&k!=i){ //같은 수 제외
					if(check[i][j]!=1 && check[i][k]!=1&&check[j][k]!=1){ //각 경우에서 먹을 수 있는 조합이 아니라면
						//printf("%d %d %d\n",i,j,k);
						cnt++;
					} 
				}
			}
		}
	}
	printf("%d",cnt);
	return 0;
}

해당 코드를 통해 문제 해결은 성공하였으나 역시 시간복잡도가 너무 커서 좋은 코딩이라고 부르긴 힘들 것 같다.