수능완성 수1 행렬과 그래프 문제 풀이방법 질문이요..ㅠㅠ
게시글 주소: https://i.orbi.kr/0003133491
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
(긴급)이걸 보고도 에리카 넣는다고? 다시생각해봐라 진심으로 조언한다 0
내신 국/영/수/사/과 2.9 whw반고 입니다.. 생기부 내용은 선생님께서...
게시글 주소: https://i.orbi.kr/0003133491
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
(긴급)이걸 보고도 에리카 넣는다고? 다시생각해봐라 진심으로 조언한다 0
내신 국/영/수/사/과 2.9 whw반고 입니다.. 생기부 내용은 선생님께서...
님처럼 경우를 나누어서 풀더라도 가능한 모든 케이스를 열거해서 확실하게 풀면 괜찮습니다. 예를 들어 꼭짓점1과 2가 연결되는 경우도 가능은 할테니 (실제로 x+y가 최대가 될 수는 없어서 제외하셨겠지만..) 그것도 따져주긴 해야겠지요.
다만, 그래프의 성질을 이용해서 x+y의 최댓값을 구해놓고, 실제로 그 최댓값을 가능케하는 configuration이 존재하는 것을, 직접 그래프를 그려봐서 확인한다면, 노가다를 줄이고 좀더 빨리 답이 맞음을 확신할 수 있을 거에요.
{1,2,3} 세 점을 모아놓고, {x,y} 두 점을 모아봅시다. 점3에서, x와 y로 변이 이어진다 해도 하나 더 이어져야 하므로, 3에서 1 혹은 2로 최소한 1개의 변은 연결되어 있어야 한다.
1,2,3에서 나가는 총 변의 개수는 1+2+3=6인데, 자기들끼리 연결된 것이 1개 있으므로, 6 - 1*2 = 4.
따라서, x+y의 최댓값은 4+2 =6. (1,2,3으로부터 x,y쪽으로 뻗어나갈 변이 최대 4개, x,y 자기들끼리 연결되면 변 2개 추가)
이렇게 따진 후, 실제로 6이 되는 그래프만 하나 찾아주면 됩니다.