• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

60. 합이 같은 부분집합

21.01.11 00:41 작성 조회수 81

0

안녕하세요, 선생님!

선생님과 코드가 약간 다른데, 제가 만드는 test case에선 정상적으로 작동하는 것 같지만

선생님의 채점파일에선 1,3에서 Wrong Answer이 나옵니다..

혹시 어느 부분에서 잘못되었는지 봐주실 수 있으실까요?

#include <iostream>

using namespace std;

int input[10], ch[11] = {0, };
int n, sum1 = 0, sum2 = 0;
bool bReturn = false;

void DFS(int x);

int main()
{
	int k;
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		cin >> k;
		input[i] = k;
	}
	
	ch[input[0]] = 1;
	
	DFS(0);
	if (bReturn == true)
	{
		cout << "YES";	
	}
	else cout <<"NO";
	
	return 0; 
	
}

void DFS(int x)
{
	if(x > n) {
		sum1 = 0;
		sum2 = 0;
		for(int i = 1; i <= 10; i++)
		{
			if(ch[i] == 1) sum1 += i;
			else if(ch[i] == 2) sum2 += i;
		}

		if(sum1 == sum2) {
			bReturn = true;
			return;
		}
	}
	
	else {
		// Move to right
		ch[input[x+1]] = 1;
		DFS(x+1);
		// Move to left
		ch[input[x+1]] = 2;
		DFS(x+1);
	}
	
	
}

답변 1

답변을 작성해보세요.

0

안녕하세요^^

1<=N<=10 이란 이야기는 주어지는 집합의 크기 즉 원소의 개수를 의미합니다. 각 원소의 크기를 따로 제시 하지 않은 제 잘못이 크네요ㅠㅠ.  문제는 원소의 크기도 보완해서 수정해 놓겠습니다.

위 코드는 ch배열의 인덱스 번호가 집합의 원소라는 가정으로 짜신 코드입니다. 배열의 인덱스번호를 어떤 데이터의 값이라고 가정하고 짤때는 이렇게 했을 때 메모리의 엄청난 낭비가 없는지 확인하시고 짜는 습관을 가지시기 바랍니다. 코딩인터뷰에서 굉장히 중요한 체크사항입니다.

만약 코딩인터뷰에서 제가 만든 문제처럼 원소의 크기가 주어지지 않은 상황일 때, 위와 같은 스타일로 짜려고 한다면 면접관에게 입력되는 원소의 크기는 어떻게 되냐고 질문을 하면 좋은 인상을 받습니다.

참고로 짠 코드가 생각과 다르게 나올때에는 중간 중간 아래 코드처럼 출력해보면서 디버그해보세요.

void DFS(int x)
{
	if(x > n) {
		sum1 = 0;
		sum2 = 0;
		for(int i = 1; i <= 10; i++)
		{
			printf("%d ", ch[i]);   //디버그 출력
			if(ch[i] == 1) sum1 += i;
			else if(ch[i] == 2) sum2 += i;
		}
		puts("");

		if(sum1 == sum2) {
			
			bReturn = true;
			return;
		}
	}