답이 좀 늦은것인지도 모르겠는데요UnLock- wrote:
형님들 제가 과제가 막혀서 그런데 좀 도와주세용 ㅠㅠ문제산타의 양말 찾기
50개의 선물 상자 중에 한 개의 상자에는 산타의 양말이 들어 있다. 다음의 조건에 맞는 양말이 들어있는 상자를 찾는 프로그램을 작성하시오.
1. 상자는 배열을 이용하여 구현, 선물 상자의 무게는 10 양말 상자의 무
게는 1로 가정
2. 상자를 여는 횟수는 1번으로 제한 (배열을 탐색하여 1인 것을 찾는 방
법은 불가)
3. 상자들의 무게를 비교하여 범위를 제한하는 함수는 재귀 함수로 작성(
비교하는 횟수는 6번 이하)
일단 조교님 힌트로는 이진 탐색이랑 비슷한 방법으로 하면 된다는데
도오오오오오오저히 답이 안나옵니다 ㅠㅠ
일단 지금까지 짠 코드는 이따 집가서 보여드릴게용 ㅠㅠ
저는 이 상자들을 3개로 나눠봤습니다.
그러니까, 50개의 상자면 17,17, 16 이렇게 세 더미로 최대한 균등하게 나눠보자는 것입니다.
그럼 첫번째 17개 상자들과 두번째 17개 상자들을 비교하면
1) 무게가 같다
2) 첫번째가 무겁다
3) 두번째가 무겁다
이렇게 세가지가 있겠죠.
1)의 경우에는 16개짜리 더미에 양말이 들어있는 것이겠죠.
2)의 경우에는 첫번째 17개 상자들 중 양말이 있겠죠.
3)의 경우에는 두번째 17개 상자들 중 양말이 있겠죠.
17, 17, 16이 아니더라도 16, 16, 18도 되겠죠.
이런 식으로 범위를 줄여나갈 수 있습니다.
이러면 최대 4번이면 양말을 찾을 수 있습니다.
c++ 코드입니다.
#include <stdio.h>
#include <random> // 랜덤을 위한 헤더
#include <time.h> // 랜덤을 위한 헤더
#pragma warning(disable : 4996) // visual studio 2013 또는 그 이상을 사용하지 않는다면 필요없음
#define NUM 50
int box[NUM];
void SetSock() // 상자 안에 양말 넣기
{
srand((unsigned)time(NULL));
int a = rand() % NUM;
printf("%d\n", a); // 확인용 출력
for (int i = 0; i < NUM; i++)
{
if (i == a)
{
box[i] = 11; // 양말이 있는 상자
}
else
{
box[i] = 10; // 양말이 없는 상자
}
}
}
int BoxSum(int a, int b) // 상자들의 무게의 합
{
int w = 0;
for (int i = a; i < b; i++)
{
w += box[i];
}
return w;
}
void FindSock(int a, int b)
{
int n = b - a; // 개수
int delta = n / 3 + 1; // 한 묶음의 상자 개수
int boxSum1 = BoxSum(a, a + delta);
int boxSum2 = BoxSum(a + delta, a + 2 * delta);
if (n == 1)
{
printf("ans : %d\n", a); // 답 출력
return;
}
if (boxSum1 == boxSum2) // 첫번째 상자들과 두번째 상자들의 무게가 같다면
{
FindSock(a + 2 * delta, b);
return;
}
else if (boxSum1 > boxSum2) // 첫번째 상자들이 무겁다면
{
FindSock(a, a + delta);
return;
}
else // 두번째 상자들이 무겁다면
{
FindSock(a + delta, a + 2 * delta);
return;
}
}
int main()
{
SetSock();
FindSock(0, NUM);
}