어케 푸는지 모루는 문제
게시글 주소: https://snu.orbi.kr/00070898908
2006개의 도시들 사이에 도로를 연결시키고자 한다. 이때, 한 도시에서 다른 한 도시로 설치된 도로를 통해 이동할 때, 이미 지나갔던 길을 다시 지나지 않고 이동하는 것을 좋은 이동이라 하자. 이때 다음 세 조건을 모두 만족시킬 수 있도록 도로건설과 통행료 책정을 할 수 없음을 보여라.
조건 1, 임의의 한 도시에서 다른 한 도시로 갈 수 있는 좋은 이동은 정확히 하나이다.
조건 2, 도시와 도시 사이를 지날 때에는 정해진 자연수만큼의 통행료를 내야한다.
조건 3, 2006개의 도시 중 두 도시를 선택하여 두 도시 사이에 좋은 이동을 할 때 지나가는 각 도로에 내는 통행료의 총합들은 1,2,3,...,2006C2로 서로 다르다.
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
국어 과탐은 뺏음 이유는 묻지 마
-
빨간머리 잘어울리는사람 빨간옷 잘어울리는사람 얼굴에 홍조 있는사람 팔꿈치, 손 마디 빨간사람 흐흐흐
-
자러감뇨 1
다들 행복한 새르비 하셈뇨
-
이나경전남친(60만중1명)
-
아니근데다들 10
이상형물어보면 뭐라 답하나여
-
점깐 졸았는데 1
쳐 먹히고 무승부 도ㅑㅆ네 ㅅㅂ
-
오늘은 여기서 끝. 10
나의 정체에 수많은 물음표를 달고 있을 그대들에게 안녕을. 꿈에서 만나.
-
샤 3
인 미 N 제 깔 깔
-
이거레알
-
찌를려고 신청한 거라 과 관련 물ㄹ 건 2개 밖에 생각이 안나네ㅁ
-
기차지나간당 17
부지런행
-
반수 망하고 나군에 지금 학교(부산대/경북대) 하나 넣었음 이때도 낙지랑 이것저것...
-
라떼는... 0
점심 시간 때 나야나 음악 방송으로 맨날 나오고 그랬어
-
물론 2학년때부터 하루 4-5시간씩 했다는.... 고3때는 최소 11시간
-
102%정도 차지중이야
-
나 진짜 문찐인게 17
소녀시대 빅뱅 gd 티아라 트와이스 태양의 후예 해품달 등등 드라마는 본적 없고...
-
없음
-
그거 보고 몇일 뒤에 재수하는친구 카톡프사가 오르비에 올린 인증사진으로 바뀐적 있음...
-
ㅇㅋ 진짜 변명 25
내가 프랜차이즈 카페를 잘 안 가서 그런 거임 나 보통 편의점 가서 레쓰비 마심 ㅇㅇ
-
아 목 아파 3
물 2000리터 마셔야지
-
오오삼이라고 불러 그럼 오우삼 아님 주의.
-
ㅇㅈ 10
-
학교 담임 쌤이 점심 시간 때 노래 틀어주곤 했음 초딩 때 애들 다 아이즈원이나...
-
저는 경제학과에요 19
근데 이것은 사실일까요
-
모솔임
-
뭐해야할지 모르겠어서 걍 롤체 하는 중 그냥 처음부터 다시 할까
-
밝은옷이 잘어울림 하늘색같은거
-
논술 학원 1
대구에 논술 학원 추천 해주세뇨..
-
한명제꼈다 야호
-
성한/중 갈 수 있는 성적인데 교원대 윤리교육이 가고싶다..
-
사람은 참 간사함 12
직년에 00대면... 어느 과나 가지 하던 난데 막상 안정이 뜨니 안 행복함. 더...
-
내가 스벅을 안 가 ㅇㅇ
-
대치 시대 대기 0
안가람t 공통 대기 걸었는데 200번대라고 하시더라고요 3월전까지 빠질 수 있을까요?,,
-
으휴 소통 단절하는 mz들
-
메가고 시대고 왜 일을 안하나 했네 이제 월요일이 된 거구나
-
살 빼거나 찌우면 예뻐짐 놀랍게도 말라서 못생긴 경우도 있음
-
열등감때매 강의 못 보겟음
-
나는 반모를 안다 ox 21
ㅇㅇ
-
작가 사람아니야 ㅠ
-
아무거나 ㄱㄱ 생각이 안나 영감받게
-
1. 가정 불화 2. 못생김 3. 약속 잡을 용기 없어서 성인 되는 새해에 혼자...
-
뭐지다노
-
이쁜 짤 좀여 9
3D
-
ㅈㄱㄴ
-
반수학과다.
-
씹어먹어도 되나요? 이미 먹고 물어보는거긴 함
-
돈 들어 (사실 동물을 별로 안 좋아하는 거긴 함)
-
2시네 0
이제 일어나야겟네..
왜 하필 2006임
그야 2006년도 문제니까
찌찌뽕
06년 문제인듯
조합론이지 이거
어지럽네 이거
감도 안오네 아니
빠르게 gpt
gpt 절대 못 품 개 버러지 ai
gpt한테 뭐 물어봐서 제대로 된 풀이를 가져온 적이 없어요 으아아악!!
좋은 이동의 정의가 이해가안되네
한 길을 2번 타지 않는거에요
트레일
머리깨진다
도로가 폐곡선을 그리면 안되는 거 같아요
조건 3을 모르겠네... 1부터 1003×2005까지면 길이 그숫자만큼 나오는건가
일단 최대한 많은 도시와 연결된 도시를 C라고 하고 그 연결된 수를 k라고 하면 k=1일때 안되고 2일때도 안되고 3일때부터는 모르겠어요 으악
조건3에서 왜 2006C2로 마무리되는거지 이것부터 이해가안감..
경우의수가 2005+2004,+...+1이니까 2005×2006/2=2006C2구만
예스
고딩수준으로 풀수있는거맞나요 맞다면 할거도없는데 자고일나면 몇시간씩 박아서 풀어보는거 시도는 해보게요
아마 될꺼 같긴한데,, 풀이를 잘 몰라서.
수형도와 연결그래프에 대한 지식이 잇는 편이 좋을거에요.