사라진 블로그! 연락 주시면 새로운 블로그 알려드립니다 ~

30일 오후 2시부터 5시까지 KCPC가 진행되었습니다. 대회 끝난지 하루도 안된 따끈따끈한 후기 쪄왔습니다
사실 과제가 많지만 저는 모릅니당 ㅎㅎ 개인전 & 오프라인은 너무 오랜만이라 재밌었습니당~ 야호!

타전공이기도 하고 신입생이기도 해서 올해는 타전공/신입생 부문으로 출전했습니당~!!
이 글은 절대 학습용/교육용 글이 아닌 뉴비보며 희망 얻어가세요~ 급의 발로 쓴 후기입니다. 저도 언젠가 성장하면 좋겠군요.

퍼솔 AC Pass 결국틀

#A 평생 새내기가 되고 싶은 유신이 (first-year) (3분 1try)
단순 구현..! 퍼솔했습니당ㅎㅎㅎㅎ(스코어보드에 1등 띄우는 거 처음이라 신났어요 >__<

#B 피카츄 라이츄 (pika) (9분 3tries)
코포도 KCPC도 B에서 삽질하는 징크스가 있는 듯 합니다ㅠㅠ
단순 구현은 맞는데 N이 날짜인 줄 알고 반복문 돌리다가 1틀
피카츄 경험치가 음수가 되는 거 모르고 1틀
ㅎㅎㅎㅎㅎㅎ 문제 좀 읽자
제가 2틀해서 이렇게 생각하는 건 절대 아니겠지만
문제가 어딘가 잘못되었다고 생각하는데
저는 경험치가 낮아지는 포켓몬 게임을 본 적이 없습니다 ㅎ..

#C KCPC는 무엇의 약자일까? (acronym) (14분 1try)
사실 문자열 보고 처음에 쫄았습니다.
설마 아호코라식...! 일 리는 없지만 설마 트라이 ...?? 둘다 절대 시간 내에 구현 불가능 ~
작년까지 문자열 입출력을 못받던 저는....ㅎ ㅎㅎ kmp도 최근에 공부했기 때문에ㅎ ㅎㅎ 머든 나오면 거릅니다.
다행히 단순 오토마타 문제였습니다. 후 뇌절말고 구현해야죠

3솔브한 시점에서 문제가 난이도 순이라는 걸 눈치챘어야 했지만 그러지 못했죠. ㅎㅅㅎ

#D 초코칩 케이크 (cake)
슬슬 어려운 문제가 나올 시점이라고 생각했습니다.
숭고한 캠프에서 세그먼트 트리를 진행했던 분이 문제에 등장하셨는데, 여기에 N제한이 30만이나 되길래
아 세그먼트 트리 문제구나! (<-아니었음) 이따 풀어야지하고 잠시 ㅌㅌ했습니다.

#E 함정에 빠진 이동관 (trap) (33분 1try)
누가봐도 단순 BFS! 뇌절말고 열심히 짰습니다.
초반이라 구현 속도도 준수했고 D를 건너뛴 덕분에 퍼솔을 먹었습니다.
근데 1등님 6분컷한 거 보고 좀 소름...

D 잠깐 다시 읽었는데 딱히 생각 안나서 또 패스

#F 대자보 (poster)
어 혹시 정수론? 점화식? 네모는 수학이 시러시러~ㅂㅂ
나중에 챙기러 돌아올까 했지만 다른 문제들에 막혀서 시간없어서 얘는 여기서 ㅂㅂ~

#G 신앙 (faith) (2tries)
빨간약 한 놈 씩 몰빵해주면서 s-h순으로 정렬해놓고 위에서부터 s-h>0인 경우에 파란약 먹이면 될 거 같았는데
풀이 자체는 어렵지 않아보이긴 합니다...만 맞왜틀
몇 번 더 틀리고 나중에 봐야지 하고 넘어갔습니다.

#H 얼마나 예뻐? (pretty)
안 예뻐요. 트리. 전위순회. ㅂㅂ

문제를 안 읽고 넘긴 건 이게 유일한데 마지막에 보니 다들 이거 붙잡고 있어서 쪼끔 후회.....ㅎ

#I ㅇㅇ (oo)
역톨레미로 후다닥 점 분류했는데 답을 출력할 때 보니까 외심의 좌표도 출력하라 하네요 ㅎㅎㅎ
꼼수따윈 통하지 않는... 문제 좀 읽자.
역톨 없어도 세 점 주면 외심 내놓는 함수 (이거 약간 뇌절...) 짜면 분류도 똑같이 할 수 있죠 ㅎㅎㅎ 머한거지
구현하기도 싫고 지금까지 뭐했나 싶어서 뇌절하다가 스코어보드 보니까 케이크가 많이 풀렸길래 잠시 Pass

#D 케이크 (66분 1try)
ㅎㅎㅎㅎ 쉬운 문제라는 걸 인지하니 풀이도 바로 떠올라서 뚝딱
너무 늦게 풀긴 했지만 다른 친구들도 나름 어디선가 삽질하고 있었는지 3등이었습니다. (문제는 이 때가 66분이었는데, 이 뒤로로 맞은 문제가 없.... ㅎㅎ )

빠가사린가.. 이 때는 진짜 문제가 난이도 순이라는 걸 조금이나마 눈치챘어야 합니다.
이 시점에서 5솔/3등이었는데 1,2등이 너무 막강하고 다른 5솔이 한 명밖에 없었기 때문에
남은 시간 동안 어떻게든 G를 고치고 I나 계속 풀어야지~ 라는 전략을 세웠습니다.
둘 중 하나만 이루면 성공하는 전략이었으나, 둘다 망해서 전략은 실패했죠

다시 G를 잠깐 보긴 봤습니다만 아무리 생각해도 반례가 떠오르지 않았습니다 ㅎㅎ
F랑 H는 끝까지 관심을 못 주었습니다 ㅠ 미안해..

#I ㅇㅇ (oo) (5tries)
2시간 이상 꼬라박았네요. 호감상으로 잘생긴 문제였습니다. 열심히 외심 구하는 공식을 짰습니다. 수직이등분선이 수평/수직일 때, 세 점이 한 직선 위인 경우 등 열심히 고려하고
대회 시작하고 두 시간 즈음 되서 완성하고 제출했는데 틀렸습니다. 틀렸습니다. 틀렸습니다. 틀렸습니다. 틀렸습니다.
ㅎㅎ 문제 인성이 참.....(제 실력의 문제죠) 이때 던지고 H를 보던 G를 고치던 해야했습니다 ㅎㅎㅎㅎ..

1시간 남은 시점에서 5솔브들이 많아졌고, 다들 무언가 시도하고 있었기에 어떻게든 하나를 풀어야 안전(?)해지는데
G는 도저히 반례를 모르겠고 F도 잠깐 봤는데 모르겠고 H는 읽기 싫었습니다.
I는 여전히 시도하는 사람이 없길래 출제자 심심할까봐, I랑 마지막까지 놀았습니당.

그렇게 저는 G랑 I를 끝까지 틀리고 5솔브/3등으로 마감햇습니당!
66분 이후로 푼 게 없는데 기도메타 성공해서 등수 3등 고정~~ㅎ

나중에 풀이 설명해주는데
아직도 G틀린 이유는 잘 모르겠습니다 흑....
I는 1. long double 미사용 2. 외심의 범위가 10^6 바깥일 수 있음의 두 가지 이유로 틀린 듯 합니다 ㅎㅎ
실수 문제 보면 맨날 넘겨서 잘 몰랐는데
double이 만능 짱짱맨이 아니란 걸 처음 알았습니다. 아니 10^12가 될 리가 없었죠 ㅎ 생각이 없었네요
그리고 문제 좀 읽자

개인전 오프라인 오랜만인데 문제가 많아서 좋았습니다.
저는 혼자 두면 네모 하고 싶은 거 다 해~~ 편식 모드이기 때문에 풀고 싶은 문제를 잡고 시간을 열심히 꼬라박는데
문제 선택에 많은 자유도가 있었기에 더더욱 즐길 수 있었지 않나 싶습니다.

기도메타 성공한 것도 너무 좋습니다. 제 실력에서 최고등수가 3등이라고 생각했는데 딱 그렇게 나왔네요 ㅎㅎㅎ
GI를 둘다 틀려버린게 아쉽지만, 둘 중 하나를 푼다고 해서 제 등수가 변하는 건 아니라서요ㅎㅎㅎ

대회후기 요약:
모두가 행복한 대회를 만들고 싶었다고 강조하셨는데,
모두가 행복한 대회는 모두가 무언가를 얻어가는(받아가는) 대회가 아닌가 싶습니다. (속마음::기념품 안 준 게 아깝...
각자 나름의 무언가를 얻어갔을 것 같은데
저는 I랑 2시간 즐겁게 놀았고, 무엇보다 20만원 너무 좋습니다 행복합니다~

21일 오전 9시부터 22일 오후 9시까지 SCPC가 진행되었습니다. 작년 포스터를 잘못 봐서 토요일로 알고 있었는데 금요일이더군요;;; 토욜 약속을 다 취소하고 금요일로 잡아놔서 밤 샜습니다 ㅠㅠ

저는 SCPC 1차 온라인 예선 후기를 찾아보면서 나오는 블로그들이 너무 갓갓하셔서 [세상은 넓고 잘하는 사람은 많아] 하구 절망했었기 때문에 저도 후기 하나 남겨봅니다.
여러분은 미천한 저를 보면서 희망을 얻어가세요.

#1 오르락 내리락 (제출 2248회 맞은 사람 1059명)
BFS로 누적합-N배열을 미리 만들어 놓으면 각각의 TC들은 O(1)로 계산할 수 있습니다.
O(N * T)

특이한게 제출했을 때 1.0000X초 정도로 틀렸습니다. 계속 내다보면 한 번 즈음은 맞지 않을까 하고 5번 냈는데 안 되더라구요ㅋㅋ 2019-10-26 추가:: 삼성이 시간제한 넘어가버리면 그냥 바로 끊고 TLE 때려서 그렇다구 하네요.
결국 cin을 printf로 바꿔서 맞았습니다. 나중에 공지 뜨네요 ㅋㅋㅋ..
그러나 6번이나 틀려서 제출횟수 패널티 때문에 상당히 긴장했습니다.

#2 공 굴리기 (제출 1323회 맞은 사람 1029명
중딩 수학문제입니다. 직선경로와 회전경로 나누어서 계산했습니다.
R<h일 때 계속 답이 다르게 나와서 한참 고민했는데 (댕청..) R<h인 경우 직선 경로가 찔끔 늘어난다는 점 고려해서 계산하면 됩니다.

#3 점프 (제출 1064회 맞은 사람 107명)
못 풀었습니다 (당당)
Hap 배열을 만들어서 i번째 칸에는 1~i까지 합 넣어두고 (영알못이기 때문에 콩글리쉬 배열명을 씁니다.)
그리디하게 y 부터 y-Hap[upperbound(Hap,Hap+Hap.size(), y)-1] (씨알못이라 문법 잘 못 외워서 틀릴 수도 있습니다.)까지만 대강 구하면 될 것 같았습니다.

근데 나중에 N=20일 때 반례 생기는 거 깨닫고 던졌습니다.
사실 삼성이 10번까지만 제출 가능한데, 9번 즈음 틀릴 때 즈음 자포자기...했습니다. (사실 4번 긁고 개이득~하고 자러 갔습니다 ㅋㅋ

듣기로는 N이 작을 때는 직접 구하고 N이 특정 이상 커지면 위에 풀이처럼 그리디 하면 된다네요.

근데 그 이전에 저는 맞왜tle... 코드에도 문제가 있었나 봐요 흑.. 다 잘했는데

#4 파이프 (제출 160회 맞은 사람 25명)
와..!! 제 수면 시간을 지켜준 고마운 문제입니다. 휴리스틱 문제 보면 다들 피하시는 것 같은데, 저도 그럽니다ㅋㅋㅋ
근데 문제 읽어보니까 출제진이 제안한 답 * 2 이내이면 점수를 준다길래, 그냥 크기 순으로 정렬해서 챠르르륵 이어붙이는 코드 뚝딱하고 제출하니 186점... ㄱㅇㄷ

#5 세포 키우기 (제출 334회 맞은 사람 102명)
하.. 1차는 통과할 것 같고 자러 가야해서 문제만 읽어봤습니다. (못 풀겠다는 핑계 맞습니다.)
문제를 읽어도 아무런 생각이 들지 않았습니다.

345는 맞은 사람이 백 명 아래군요. 특히 4번 25명 ㄷㄷ...저도 그렇고 다들 아직 휴리스틱 기법에 익숙하지 않나봅니다. 저는 유명하거나 쉬운 알골만 공부하기 때문에 푼 사람 수를 보니 아직은 공부 안해도 될 것 같습니다. (따라하지 마세요)

그렇게 저는 4번의 혜자로운 부분점수 받고 386점으로 마감했습니당~ 온2차 분들 깔아드리겠습니다ㅎㅅㅎ

구현 문제입니다. (이 게시판은 불친절 모드 게시판입니다)

[Baekjoon Onine Judge]

#1406 에디터

https://www.acmicpc.net/problem/1406

Problem Solving Strategy

구-현 문제입니다. 리스트 써도 되고, 스택 써도 됩니다.

알고리즘 문제라기보다 구현이 까다로운 문제라 머 드릴 말씀이 없네요ㅎㅎ..

전 리스트로 풀다가 머리쓰느라 고생했는데, 큐로 풀면 어떨지는 모르겠씁니당.

0.3초라 시간 최대한 단축하려고 구조체로 구현했습니다.

저는 함수 안 쓰고 풀었기 때문에 모르겠는데

list 라이브러리나, 함수는 O(1)이어도 호출 시간이 길어서 시간 초과 날 수도 있을 거에요.

(사실 시간복잡도 계산 안해봐서 몰라요 ㅋㅋ 될 수도 이써요... 여기는 불친절모드 설명 게시판이니까용)

전체 코드 보기

문자열 입력받는 거를 잘 못해서, 입력 받는데만 1시간 쏟았네요 ㅂㄷㅂㄷ...

첨 알았는데 scanf가 for문 안에 들어가니까 난리나더라구요 ㅎㅎ(?);;

gets()로 편하게 받았는데, 해당 문법이 C++14에서 삭제되서, gets()를 쓰고 싶으시다면  C++11로 제출해야합니다^^;;

...입력을 예쁘게 못 받은 듯 싶습니다....한두개 더 줄일 수 있을거 같지만

더 이상 코드를 수정할 기력이 없기에 .... 총총/

Educational Codeforces Round 49(Rated for Div.2) #C Minimum Value Rectangle 문제풀이입니다.
문제링크입니다.

http://codeforces.com/contest/1027/problem/C

Problem Solving Strategy


수학 문제입니다.
문자로 나타내어 식을 열심히 변형하면 결론은 a/b+b/a가 최소가 될 때 각각의 a, b를 구하는 문제와 동치입니다.
그래프를 그려보면, 사실 a, b각각의 값이 중요한게 아니고, 비율이 중요하죠.
b>a라고 했을 때 a/b가 1에 가까울수록 a/b+b/a가 최소가 되겠죠.

코딩 전략

n이 10^6이라는 좀 큰 범위긴 하다만,
사실 an의 범위 해당하는 1부터 10^4까지의 숫자가 2번 나타나는지 4번 나타나는지가 중요합니다.
따라서 배열 크기는 10^4로 잡아줍니다.
입력받으면서 1~10000까지의 숫자가 각각 몇 번 나타나는지 기록하는데,
2번 나타날 때거나 4번 나타날 때, b라는 새로운 배열을 만들어서, 기록합니다.
4번 이상 나타난 수는 두 번 기록되고, 2-3회 등장한 수는 한 번 기록되겠죠.
b라는 배열을 정렬합니다. 왜? 비율이 최소가 되는게 궁금하니까, 인접해있는 수만 비교하면 됩니다.


예를 들어 1, 2, 8, 11 세 숫자 중 비율이 최소가 되는 두 수를 고르려면
1과 2 / 2와 8 / 8과 11 이 세 경우만 비교하면 되겠죠?


열심히 비교해서 최소가 되는 경우 체크한 뒤, 나중에 출력합니다.

틀리는 경우

시간 초과 나는 경우에 대해 생각해보자면, (사실 제가 걸린 거)

코딩 편하게 하려고
b배열을 잡지 않고, 그냥 a배열을 훑으면서 풀려고 하다가,,,
n=6으로 T가 왕창 많이 들어왔을 경우 O(10000*T)>2~3초로 가볍게 넘어가버렸습니다...;;;

전체 코드 보기

오늘의 문제는 2005년도 KOI 시.도 지역본선 2번인 [놀이공원]이에요.

#1931 회의실배정과 비슷하게 시작시간만을 보며 정렬한 뒤(회의실배정은 종료시간으로 정렬하죠 ㅎㅎ) 앞에서부터 탐색하며 풀이해도 풀리지만, 그러한 풀이는 이미 친절하게 포스팅 되어있어서, 저는 다른 방식으로 풀이해보았어요.

라인 스위핑의 기초 중의 기초 형태인데

#10714 JOI 2015년도 1번 기차여행 역시 본 풀이에서 사용한 기법을 이용하여 간단히 풀려요.

[Baekjoon Onine Judge]

#2594 놀이공원

https://www.acmicpc.net/problem/2594

2005 한국정보올림피아드 시.도지역본선 고등부 2번

Problem Solving Strategy

하나라도  놀이기구가 운행 중이면, 철수와 영희는 데이트를 하지 못합니다.

반대로 말해, 우리가 확인해야하는 것은 '모든 놀이기구가 정지해있는가'에 대한 여부만 확인하면 됩니다.

지금 특정한 어느 놀이기구가 운행중인지는 궁금하지 않습니다.

문제 해결 아이디어는 간단합니다.

어떤 놀이기구의 운행 시작시간은 종료시간보다 반드시 앞서지요.

시간 순서대로 탐색하며 어떤 놀이기구의 운행이 시작할 때 +1을 하고 종료할 때 -1을 계산해주면, 그 순간에 몇 대의 놀이기구가 운영중인지를 알 수 있으며, 변수가 0이 될 경우에는 모든 놀이기구가 정지한 것입니다.

일단 입력을 꼼꼼하게 받아봅시다.

1.입력은 분 단위로 받아줍니다.

분 단위 출력만 하면 되므로 이 편이 뒤에서 변수를 다룰 때 코딩이 편하므로 당연하겠지요.

운행 10분전부터 10분 후까지도 철수와 영희는 만나지 못하므로, 해당 시간 역시 고려하여 받아줍시다.

2. 시작시간과 종료시간을 각각 오름차순으로 정렬합니다.

정렬하며 어느 놀이기구의 시작시간과 종료시간을 매칭시킬 정보는 잃지만, 저희는 단지 어느 순간에 놀이기구가 시작하거나 종료했는지만 궁금하므로, 편하게 따로 정렬합시다.

3. 시간 순서대로 탐색하며 시작과 종료의 개수를 카운팅합니다.

시간 순서대로 탐색하며 어떤 놀이기구의 운행이 시작할 때 +1을 하고 종료할 때 -1을 계산해주면, 그 순간에 몇 대의 놀이기구가 운영중인지를 알 수 있으며, 변수가 0이 될 경우에는 모든 놀이기구가 정지한 것입니다.

틀리기 쉬운 부분

저는 22시를 분으로 변환하다가 13200이라 계산해서 제출 횟수를 상당히 낭비했지만... ㅋ...

코딩만 꼼꼼히 한다면 거의 없습니다.

4. 극단 값을 계산할 때 음수가 발생하지 않을까

입력을 받을 때 편하게 무차별적으로 10을 가감하고 받았는데 걱정할 법도 하지만 3번 질문의 코드처럼 MAX를 0이로 선언하고 항상 비교 후 갱신이 일어나도록 하면 걱정하는 일은 잃어나지 않음이 증명됩니다.

마지막으로 하루 일과를 시작하는 시간과 끝내는 시간을 고려하여 코딩을 마무리해줍니다.

전체 코드 보기

블로그에 공개를 하기 위해 코드가 많이 얌전해졌는데, 보통 굉장히 지저분하게 코딩을 해왔어서 그 습관이 여기저기 들어 있을 거 같아 피드백은 언제나 환영해요 *^~^*

숫자구슬은 Parametric Search 를 알고 계셨다면 쉽게 풀으셨을겁니다. 이분 탐색을 이용하여 결정 문제를 해결하는 기법이에요.

[Baekjoon Onine Judge]

#2613 숫자구슬

https://www.acmicpc.net/problem/2613

2004 한국정보올림피아드 시.도지역본선 고등부 4번

Problem Solving Strategy

Parametric Search에 대해 알고 있거나, 이분탐색이나 나무자르기 같은 문제를 풀어보았으면 바로 떠오를 것입니다. ^=^

어쨌든 Parametric Search로 문제를 풀어봅시다.

1. 무엇을 이분탐색할 것인가?

범위로 주어진 것이 정답의 범위밖에 없으니까 정답의 범위를 이분탐색 해봅시다.

N은 300이하이고, 구슬의 숫자는 100이하이므로 정답의 범위는 30000이하이겠죠?

left는 1로 right는 30000으로 잡아줍시다.

2. 어떻게 판단할 것인가?

어떨 때 왼쪽으로 가고, 어떨 때 오른쪽으로 갈까요?

보통 문제의 조건에서 판단의 기준이 찾아져요.

이 문제에서 수치화된 조건은 그룹의 개수, 정답인 그룹의 구슬의 개수가 있네요.

아무래도 전자가 끌리죠?

답(mid)이 정해지면, 최소 그룹의 개수도 정해집니다.

How?

처음 구슬부터 시작해서 구슬의 합이 mid를 넘지 않을 때까지 한 그룹으로 묶어주면 되기 때문입니다.

그러면 구슬의 합이 mid를 넘지 않는 경우 그룹의 최대 개수가 정해집니다.

그룹의 최소 개수가 M보다 크면 정답이 아니죠? 오른쪽을 탐색해나갑니다.

작으면 그룹을 분할하여 M개가 될 수도 있으니, 일단 기존의 answer과 비교하여 mid가 더 작을 경우 answer를 mid로 바꾸고 왼쪽을 탐색해나갑니다.

틀리기 쉬운 부분

사실 이 부분은 어떻게 풀었고, 어떻게 구현했는가에 따라서 각자 다른 오답노트를 작성하게 되겠지만, 제 경우입니다.

3. 만약에, 구슬이 mid보다 클 경우에는?

저격데이터라 부르기도 민망한 케이스죠. 제가 걸렸으니까 포스팅에 넣어봅니다ㅋㅋㅋ

이경우 탐색은 무조건 오른쪽이니까, 아까 2번 과정의 첫 번째 코드에 있는 for문 안에 다음과 같은 if문을 넣어 해당 케이스를 표기합니다.

그리고 두 번째 코드에서 if(오른쪽을 탐색할 것인가)에 오른쪽을 탐색한다!라고 명령합니다.

뭐 다양한 해결방법이 있겠지만 저는 위처럼 해결했습니다.

그리고...

꽤나 (제가) 찾기 어려웠던 케이스인 아래 상황을 소개합니다!

4. 한 그룹에는 하나 이상의 구슬이 있어야 한다

이렇게 들으니 감이 잘 안 올거에요. 이게 왜 저격 데이터야? 묻는 사람이 있을 겁니다.

보통 코드 구현 과정에서 각 그룹을 구성하는 구슬의 개수를 출력할 때, 이진탐색을 도는 과정에서 저장을 하거나, 이진탐색에서의 코드를 아래에 복붙한 뒤, mid만 answer로 바꾸어서 출력을 합니다.

그리고 맞았습니다가 뜨기를 기도하며 제출을 하지만

결과는 틀렸습니다.

네. 저도 그랬습니다 ㅋㅋㅋ캬캬ㅏ

문제를 잘 읽어보면 최대값과 각 그룹을 구성하는 구슬의 개수를 출력해야합니다.

현재 mid가 2일 때 

4 2

1 1 2 1 이라고 입력해봅시다.

그러면 그룹 분류가 다음과 같이 됩니다.

(1,1) (2) (1)

그럼 그룹의 구슬 개수를 출력이 다음처럼 나오겠죠?

2 1 1

넵. 틀렸습니다.

결과를 출력하기 전에

세어진 그룹의 개수와 M을 비교한 뒤

부족한 그룹의 개수만큼

중간에 구슬의 개수가 2개 이상인 그룹을 분할해서 해결해줍시다.

전체 코드 보기

시.도지역본선 초반 번호대의 문제다운 난이도로, Floyd-Warshall Algorithm (플로이드 와샬)을 이용해, 간단히 해결되는 문제입니다.

[Baekjoon Onine Judge]

#2610 회의준비

https://www.acmicpc.net/problem/2610

2004 한국정보올림피아드 시.도지역본선 중등부 3번

2004 한국정보올림피아드 시.도지역본선 고등부 3번

Problem Solving Strategy

다음과 같은 세 부분으로 나누어 생각을 해야지! 라는 생각이 떠오를 것입니다.

1. 모든 사람에 대해 플로이드 와샬 알고리즘을 돌린다.

2. 조건에 맞게 위원회를 구성한다.

3. 위원회의 대표를 찾는다.

1. 모든 사람에 대해 플로이드 와샬 알고리즘을 돌린다.

위원회의 대표를 찾는 과정에서, 플루이드 와샬 알고리즘이 필요하다는 것은 깨달았을 것입니다.

각각의 위원회에 대해 돌려도 되지만 코드가 불필요하게 길어지며, 모든 사람이 같은 위원회에 속하는 경우의 수도 존재하므로

처음에 그냥 모든 정점을 집어넣고 돌립니다.

2. 조건에 맞게 위원회를 구성한다.

3. 위원회의 대표를 찾는다.

굳이 각 위원회의 정보를 저장할 필요가 없으므로,  imsi로 그룹원을 저장하는 배열을 만들고 대표를 찾은 뒤, 각 그룹의 대표만 저장해도 됩니다. 본인은 반복문 탈출 조건을 N명의 사람을 모두 방문했을 때로 했습니다.

전체 코드 보기

블로그에 정리할 생각을 하지 않고 짰던 거라 변수명과 코드가 조금 지저분..해요 ㅠ-ㅠ