|
:: 게시판
:: 이전 게시판
|
- 모두가 건전하게 즐길 수 있는 유머글을 올려주세요.
- 유게에서는 정치/종교 관련 등 논란성 글 및 개인 비방은 금지되어 있습니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
22/08/17 18:20
되게 문학적이지 않나요 크크크크. "대학교수는 문제에 만들 쓸만한 컨텐츠를 위해서 지구를 파괴했다"
크으 이게 서사고 플롯이고 감동이고 소설이죠!
22/08/17 17:59
문송한 제가 친구에게 열심히 물어봐서 제가 이해한 버전 입니다!
'지구/우주정거장'이 있고, '화성' 이렇게 공간이 두 곳이 있습니다. 지구는 망해서 남은 인류는 N명입니다 (문제에 이 숫자는 크게 중요하지 않음), 이 N명의 인구를 '한 명씩' 교수님이 조수석에 태워서 화성으로 옮길 것입니다. 그런데 교수님이 가지고 있는 M개/줄의 리스트에는 한 개/줄마다 악질 정떡분탕 3명의 이름이 적혀있습니다. 이 정떡들은 지구나 화성에 모여있고 '교수가 떠나면' 그곳을 터트립니다. 이걸 '게임오버'라고 칩시다. 당연히 시작하자마자 글려먹은 세계선도 있습니다 (교수가 맨처음에 누구를 화성으로 데리고 가도 지구는 남아있는 분탕 조합에 따라서 터짐) 반면에 '게임성공'인 세계선도 있습니다. 예를 들어, 리스트가 10,000 즉 1만개짜리인데, 10001번, 10002번, 그리고 1부터 10000까지의 사람으로 구성되어있다면, 교수는 10002번 인간만 지구에 남겨뒀다가 마지막에 화성에 내려놓으면, 인류는 정떡 폭발 없이도 화성에서 행복하게 살수 있습니다. 매 세계선을 들여다보고 '게임오버(NIE)'와 '게임성공(TAK)'을 계산해서 뱉는 알고리즘을 코딩하는게 목표가 되는 것이고요~ 제한시간은 7초입니다 흐흐. 그냥 무한대입은 안되니 '알고리즘'을 만들어와라!
22/08/17 17:46
학교 선배가 만든 사이트인데, 알고리즘 문제 사이트 중에서는 가장 유명한 곳이에요
문제 빡세보이긴 한데 알고리즘 문제풀이 손 놓은 지 오래되서 생각나는 게 없네요 ㅠ
22/08/17 17:52
생존자 중에 3명이 한 공간에 다 모이면 다 죽는데 어찌 다 이동할 수 있나요?
저 3명 중 한명은 빼고 넘어와야 할 것 같은데
22/08/17 17:53
교수가 같이 있으면 되요
기본적으로 주어지는 테스트케이스에서는 1번이 항상 포함되어있으니 제일 먼저 옮기거나 제일 마지막에 옮기면 되죠.
22/08/17 17:52
(수정됨) 지구나 화성이나 무조건 목록들에 맞는 셋이 모여있으면 안되는거죠?
dfs 나 bfs로 브루트포스 말고는 생각나는 방법이 없는데, 이대로 풀면 7초 넘을듯..
22/08/17 17:56
무슨 문제인지는 샘플 케이스보고 감이 왔네요
사공이 뗏목으로 이동시킬때 2개만 이동 시킬 수 있고 사공이 없을때 특정조건이 만족되면 실패가 되는 문제를 세가지 숫자로 지정한 문제네요
22/08/17 18:02
그렇습니다. 사실 문과들에게도 익숙한, 뗏목을 통해 강을 넘어가는데, 늑대는 양을 먹고, 양은 풀을 먹고 같은 문제의 변형이라고 생각하니까 저도이해가 가더라고요. 결국 모든 리스트에 들어가있는 정떡인싸 부분집합 C를 알고리즘적으로 분리해서 C의 숫자를 C=0, C=1, C=<2 같이 최적화하는게 방법인걸로...
22/08/17 18:45
만나면 터지는게 아니라 '만난 상태에서 교수가 그들을 두고 다른 사람을 태우고 떠나면' 터지기 때문에 수학적으로는 숫자가 커져도 몇몇 '게임성공'의 경우가 생깁니다. 그래서 어려운 문제가 됩니다~
22/08/17 21:56
네 대부분의 시간대에서는 사실 시작부터 터지는게 맞습니다. 그러나 M이 아무리 커도, 3명의 이름만 뽑을 뿐이지, 문제에서 설정한 최대 숫자인 25,000개의 리스트라고 해도 중복을 막은것은 아니기에 극단적으로는 25,000개의 동일한 이름이 반복되면 쉽게 피해서 인류가 살수 있습니다. 근데 이걸 어떻게 모든 경우를 계산하는 프로그램을 만들지 저도 궁금하네요
|
||||||||||||
