흥미돋 미술관의 인건비를 최대한 절감하는 방법

[흥미돋는글]

출처: https://www.fmkorea.com/8564934243

당신 소유의 미술관은 현재 심각한 적자에 시달리고 있습니다

돈을 어떻게 충당할지 고민하던 중, 삼삼오오 모여 노가리를 까고 있는 경비원들이 당신의 눈에 들어옵니다

당신은 꼭 필요한 인원만 남기고 나머지 인원을 정리해고 하고자 합니다

남겨야 하는 경비원은 몇 명일까요?

세 가지 가정:

1. 경비원은 한 자리에 고정된 채 경비를 선다

2. 경비원의 시야는 무한하고, 시야각에는 제한이 없다

3. 단, 위치 상 벽에 가려져 보이지 않는 부분은 감시할 수 없다

위의 조건에 맞춰서 필요한 경비원의 수를 계산해보자

미술관이 다음과 같이 간단하게 생긴 구조라면,

단 한 명의 경비원 만으로도 충분히 모든 구역을 감시할 수 있음

(경비원이 다른 곳을 보는 동안 뒤로 도둑이 드는 상황은 고려하지 않도록 하자)

그럼 다음과 같이 총 3m개의 벽이 있는 복잡한 형태의 미술관에는

모든 구역을 커버하기 위해 최소 몇 명의 경비원을 배치해야 할까?

이렇게 뾰족하게 튀어나온 꼭짓점에 경비원을 한 명씩 배치한 다음에

복도 전체를 감시하는 경비원까지, 총 m+1명 세워 놓으면 될 것 같은데?

아니, 1번 경비원의 자리를 왼쪽 위로 옮겨 놓으면 한 명을 굳이 더 고용하지 않고도

모든 구역을 충분히 감시할 수 있음!

그렇다면 여기서 질문:

총 n개의 벽, 즉 n개의 꼭짓점이 있는 미술관에는 몇 명의 경비원이 필요할까?

가장 간단한 예시를 들어보자

위의 그림처럼 꼭짓점이 3개 있는 삼각형 모양의 구역에 경비원이 총 3명이 있지만

사실 나머지 2명은 필요 없는 인력임

왜냐? 두 명이 없어도 나머지 한 명이 모든 구역을 커버할 수 있거든

따라서 우리는 하나의 삼각형 구역의 꼭짓점마다 

서로 다른 색의 옷을 입힌 경비원을 한 명씩 배치할 거야

왜 이렇게 하는지는 나중에 가면 알게 됨

이제 12개의 꼭짓점을 가진 복잡한 구조의 미술관을 생각해보자

이렇게 꼭짓점끼리 적당히 이어 여러 개의 삼각형 구역들로 분할한 다음

각 삼각형마다 파랑, 빨강, 노랑 경비원들이 여러 명 들어가지 않고

한 삼각형 구역에 각 색깔의 경비원이 딱 한 명씩만 들어갈 수 있도록 적절히 배치해 주자

그렇게 배치하는 방법이 없으면 어떡하냐고? (4색 문제)

다행히 3가지 색깔만으로 배치하는 방법이 존재한다는 걸 누군가가 증명해 놓았음

증명 과정은 귀납법을 이용하는데 간단히 설명하면

1. 3개의 꼭짓점을 가진 도형(삼각형)은 자명하게 배치할 수 있고

2. k개의 꼭짓점을 가진 도형에 배치할 수 있다고 가정하면

3. k+1개의 꼭짓점을 가진 도형은 적절한 대각선으로 분할해서 꼭짓점 개수를 줄인 다음 각각 배치한 후에 다시 합치면 되겠지

그런데 앞서 말했듯이 한 삼각형에는 딱 한 명만 있어도 된다 그랬지?

그러니까 위 그림의 색칠한 부분에서 있는 노란색, 빨간색 경비원 4명은 필요 없는 인력임

따라서 같은 색 옷을 입은 경비원만 남기고 모두 해고하면

다음과 같이 4명의 경비원 만으로도 모든 구역을 커버할 수 있음

만약 꼭짓점의 개수가 3의 배수가 아니라면,

같은 방법으로 경비원들을 적당히 배치한 다음에 가장 적은 색깔만 남기고 모두 지우면 되니까

필요한 경비원 수는 다음과 같음

따라서 꼭짓점이 n개인 미술관이 어떤 모양을 하고 있더라도, 

⌊n/3⌋명의 인원으로 충분히 모든 구역을 커버할 수 있음

( ⌊ ⌋ 기호는 내림 기호임 : e.g., ⌊5.6⌋ = 5 )

물론 반드시 이만큼 필요하다는 건 아님

앞에서 육각형 모양의 미술관에서는 중심에 딱 한 명 배치하는 걸로 끝났잖아

이만큼 있으면 적어도 경비원 숫자가 부족하진 않다, 는 얘기

* 틀린 부분이나 오류가 있으면 댓글 남겨주시면 감사하겠습니다

[니애비게이션]

재밌다ㅋㅋㅋ

[윈디웬디]

너여....너를 문다....

[이녹]

와 오랜만에 뇌 쓴 기분 좋다ㅋㅋㅋ

[doordie]

걍 넉넉하게 써ㅠㅠ 절대 이해 못해서 그러는거 아님

[안경올려안경내려]

페페야 반갑다

[당신의근처]

인력난인데 많이 뽑아서 써줘,,

[산책가고바람쐬기]

몰라

[레이비로션]

미술관 문 닫습니다

[유인나,]

그만알아보자,,

[어의업내]

오 신기해..뭔가 레이튼교수 게임에 퀴즈로 나올 것 같은 주제야ㅋㅋㅋㅋㅋㅋㅋㅋ

[뿡뿡아]

똑똑하다

[엑그타루트]

네?

[방바닥여포]

근데 이렇게 하면 안 돼?

[방바닥여포]

아 다시 읽으니 저렇게 두면 부족하지는 않다 의미구나 더 적을 수도 있고... ㅇㅋ 글 잘 안 읽었다

[가나마아]

존잼

[꿈나방]

네???

[개비깨비]

와 재밌다 똑똑해지는 기분이야

[희미한 빛을 난 쫓아가]

와 너무 재밌어!!!
모든 다각형은 꼭짓점만을 연결한 여러 개의 삼각형으로 분할할 수 있다는 게 오목다각형에도 적용되는 얘기였나 보네
이거 진짜 똑똑한 발상이다
글쓴 여샤 혹시 저거 중간에 등장하는 이론들 출처 알려줄 수 있나요??

[눈을포테이토오]

이거 왜 익숙한가 했더니 알고리즘 과목에서 배웠던걸로 풀 수 있을듯
삼각형으로 나눈 다음 그래프 색칠하기 문제로 풀 수 있을듯



오.... 지피티한테 물어봤더니 맞구만 ㅋㅋㅋㅋㅋ
np hard 문제엿다내요.

[업로더여시 고마워]

롸 !!!!!! 너무 재밌다!!!!

[몇요일]

수학경시대회 문제 같애 (물론 경시대회 나가본 적 없음!!)

[그라데이션인생]

뭔말인지하나도 몰르겠음 흑흑

[호랑나비한마리가]

무슨말이죠

[아세희BO]

보석상이 손해!

[설ving]

와 나 이따 꼭 다시 온다

[초사랑스러움]

모모모모르겟어요

[다음카페[Daum]]

🤖 인기글 알림 봇 🤖

* 여시 개인이 개발한 봇 입니다.
* 인기글은 최대 3번까지 기록됩니다.
* 다음카페 공식 기능이 아님을 알려드립니다.

========== ※ ========== ※ ==========
🎉 2025년 06월 24일 22시 → 인기글 75위 달성!

[오이주스]

재밋다 ㅋㅋㅋ

[영양제챙겨먹끼]

어지러워요헴….

[수초 키우기]

우리 같이 도둑질 안 하기로 꼭 꼭 약속하고 경비원 0명하자..

[디로리리리]

우와

[히힉호무리]

재미있다 ㅋㅋㅋㅋ

[둔둔댄스]

와 죤잼이다 은퇴가 싫은 근무자는 적은 색상의 근무복을 받기를..

[나는나야신조]

잼따

[곰브리치야 내 이름 적어둬라]

ㅇ오 재밌다