수능완성 수1 행렬과 그래프 문제 풀이방법 질문이요..ㅠㅠ
게시글 주소: https://image.orbi.kr/0003133491
EBS복습하다가 이런문제가 있어서 옛날에 푼거확인해보니까 2번째 그림과 같이 풀었더라구요
생각과정은
x+y=최대가 되려면 연결된 변의 갯수가 1,2,3인 꼭지점이 연결된 변의갯수가 x,y 에 최대한 연결되있음 되겠구나...
1의 경우를 보면
(x+y를 구하는것이므로 x,y어디에 연결하든지 상관없다고 생각)
1,2을 모두 x,y에 연결시 3을 연결하려면 불가능하므로 X -> 1,2과 한개가 연결되있어야하겠구나 생각
그래서
2의 경우(2-3이 연결된경우)
그림과같이 x+y=6
3의 경우(1-3이 연결된경우)
그림과같이 x+y=5
그래서 답 6
이렇게 풀엇는데 해답지나 EBS강의보면 부등식,행렬식가지고 풀던데 이런 풀이는
만약 다른 문제였지만 같은 형식의 문제였다면 시행착오가 있을수도 싶고 그런데
이렇게 푼거에 대해 잘못풀엇다던가 올바르지못하다던가 그런게잇나요..??
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
님처럼 경우를 나누어서 풀더라도 가능한 모든 케이스를 열거해서 확실하게 풀면 괜찮습니다. 예를 들어 꼭짓점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이 되는 그래프만 하나 찾아주면 됩니다.