UnLock- wrote:
형님들 제가 과제가 막혀서 그런데 좀 도와주세용 ㅠㅠ문제산타의 양말 찾기
50개의 선물 상자 중에 한 개의 상자에는 산타의 양말이 들어 있다. 다음의 조건에 맞는 양말이 들어있는 상자를 찾는 프로그램을 작성하시오.
1. 상자는 배열을 이용하여 구현, 선물 상자의 무게는 10 양말 상자의 무
게는 1로 가정
2. 상자를 여는 횟수는 1번으로 제한 (배열을 탐색하여 1인 것을 찾는 방
법은 불가)
3. 상자들의 무게를 비교하여 범위를 제한하는 함수는 재귀 함수로 작성(
비교하는 횟수는 6번 이하)
일단 조교님 힌트로는 이진 탐색이랑 비슷한 방법으로 하면 된다는데
도오오오오오오저히 답이 안나옵니다 ㅠㅠ
일단 지금까지 짠 코드는 이따 집가서 보여드릴게용 ㅠㅠ
공책에 한번 직접 해봤는데, 50개 기준으로는 6번정도만 확인하면 충분히 알수 있더군요
e.g. (25, 25) -> (12, 13) -> (6, 7) -> (3, 4) -> (2, 2) -> (1, 1)
50의 경우엔 25, 25로 나눈 다음부터는 똑같이 나눌수가 없는 상황이 되긴 하는데
어짜피 상자 하나의 무게가 10이라면 한개가 더 있다고 해서 문제가 되진 않을겁니다
12, 13을 기준으로 봤을때, 만약 12쪽에 10이라는 무게의 상자가 있다면 각각 무게는 21, 13이 될테고
13쪽에 10이라는 무게의 상자가 있다면 각각 무게는 12, 22가 될테니까요.
코드가 이상하게 되긴 했지만, 굳이 작성한다면 이런느낌이 되겠네요
C++
#include <iostream>
#include <algorithm>
int nyaa(int *arr, unsigned int size, int val) {
if (size == 0)
return -1;
if (size == 1 && arr[0] == val) {
return 0;
}
else if (size == 1 && arr[0] != val) {
return -1;
}
unsigned int del = size / 2;
int left = std::accumulate(arr, arr + del, 0, std::plus<int>());
int right = std::accumulate(arr + del, arr + size, 0, std::plus<int>());
if (left > right) {
int ret = nyaa(arr, del, val);
return (ret != -1) ? (size_t)arr + (size_t)ret - (size_t)arr : ret;
}
else if (left < right) {
int ret = nyaa(arr + del, size - del, val);
return (ret != -1) ? (size_t)arr + (size_t)del + (size_t)ret - (size_t)arr : ret;
}
else {
return -1;
}
}
int main()
{
int arr[50];
std::fill_n(arr, 50, 1);
srand(time(0));
arr[rand()%50] = 10;
int search = nyaa(arr, 50, 10);
if (search == -1) {
std::cout << "Not found" << std::endl;
}
else {
std::cout << "Found: arr[" << search << "] == " << arr[search] << std::endl;
}
}