문제
효율적으로 계획하기(2)
하루에 강좌 아홉 개가 열립니다. 강좌마다 시작 시각과 끝나는 시각이 정해져 있습니다. 고른 두 강좌는 시간이 겹치면 안 됩니다. 가장 많이 들을 수 있는 강좌 수를 구합니다.
사고력 · 초6-2 최적 설계
내 답
조심 짧은 강좌부터 고르고 싶지만 일찍 끝나는 것부터 골라야 가장 많이 듣습니다.
풀이 과정
전략 그림 그리기 — 표에 적힌 아홉 쌍의 시각을 눈으로만 비교하기는 어렵습니다. 그런데 6시부터 20시까지 이어지는 하나의 시간 띠 위에 강좌를 아홉 개의 막대로 그려 놓으면, 어디가 겹치는지도 하루 중 어디가 비어 있는지도 한눈에 보입니다. 두 번째로 할 일은 강좌를 다시 정렬하는 것인데, 표에 적힌 순서도 아니고 시작 시각 순서도 아닌 '끝나는 시각' 순서로 늘어놓습니다. 가장 일찍 끝나는 강좌가 하루의 남은 시간을 가장 많이 남겨 주기 때문입니다. 이렇게 정렬해 두면 수백 가지 조합을 뒤질 필요 없이 왼쪽에서 오른쪽으로 한 번만 훑으면 됩니다. 그 훑는 과정 자체가 빠짐없이 나열하기이고, 여기서 실제 시간표가 나옵니다. 반대로 '더는 못 늘린다'를 보이려면 강좌가 아니라 시각을 봐야 합니다. 아홉 강좌가 하나도 빠짐없이 진행 중인 시각을 몇 개만 찾아내면, 아영이가 듣는 강좌들은 서로 다른 시각을 하나씩 차지할 수밖에 없으므로 그 시각의 개수가 곧 답의 한계가 됩니다.
1STEP 1
아홉 강좌를 하나의 시간 띠 위에 그리기
아홉 강좌를 한 시간 띠 위에 그립니다.
시간 띠로 그리면 '이 둘이 겹치나?'라는 질문이 '이 두 막대가 닿나?'로 바뀝니다. 네 개의 수를 한꺼번에 비교하는 대신 눈으로 보고 답할 수 있게 됩니다.
3.MD.A.1Draw A Diagram2STEP 2
끝나는 시각 순서로 시간표를 다시 정리하기
끝나는 시각 순서로 다시 정리합니다.
끝나는 시각 순으로 줄 세우는 일은 시각 아홉 개를 크기 순으로 늘어놓는 것뿐인데, 이 문제의 핵심인 '일찍 풀려나야 더 들을 수 있다'가 그대로 담겨 있습니다.
3.MD.A.1Organize Information In More Ways3STEP 3
가장 일찍 끝나는 강좌부터 이어 붙이기
일찍 끝나는 것부터 이으면 네 과목이 붙습니다.
7{:}00→10{:}00, 11{:}00→13{:}00, 14{:}00→17{:}00, 18{:}00→20{:}00
고를 때마다 하는 일은 '이 강좌는 내가 나온 뒤에 시작하나?'라는 시각 두 개의 비교뿐입니다. 매번 가장 일찍 끝나는 것을 고르니 다른 어떤 선택도 이보다 더 많은 시간을 남겨 줄 수 없습니다.
4.OA.A.3Make A Systematic List4STEP 4
네 과목이 정말 겹치지 않는지 확인하기
네 과목이 서로 겹치지 않습니다.
10{:}00 ＜ 11{:}00, 13{:}00 ＜ 14{:}00, 17{:}00 ＜ 18{:}00
시간표를 점검할 때는 이웃한 것끼리만 확인하면 충분합니다. 각 강좌가 다음 강좌보다 먼저 끝나기만 하면 하루 전체가 겹침 없이 굴러갑니다.
3.MD.A.1Make A Systematic List5STEP 5
아홉 강좌를 모두 붙잡는 네 시각 고르기
아홉 강좌를 모두 붙잡는 네 시각을 고릅니다.
4 + 2 + 2 + 1 = 9
어느 강좌끼리 겹치는지 따지려면 짝을 36가지나 살펴야 합니다. 대신 시각 네 개를 정해 놓고 '지금 하고 있나?'를 아홉 번만 물으면 훨씬 작은 문제로 끝납니다.
3.MD.A.1Change Focus Count The Complement6STEP 6
시각의 개수로 답을 네 과목까지 묶어 두기
한 시각에 한 과목뿐이라 넷을 넘지 못합니다.
1시각당 많아야 1과목 × 4시각 = 4
의자 네 개에는 아이가 많아야 네 명 앉는 것과 똑같은 이치입니다. 시각 네 개는 겹치지 않는 강좌를 많아야 네 개까지만 담을 수 있습니다.
4.OA.A.3Change Focus Count The Complement잘 고른 네 순간이 모든 수업을 붙잡으므로, 들을 수 있는 수업은 넷을 넘을 수 없다.
왜?
모든 수업이 그 네 순간 가운데 하나에서 진행 중이므로, 다섯 번째 수업을 들으려면 다른 수업과 순간을 나눠 써야 한다.
🧱상자보다 물건이 많으면 한 상자에 겹친다상자 n개는 하나씩이면 최대 n개까지만 담으므로 n 더하기 1번째 물건은 갈 새 자리가 없어 반드시 겹친다.
왜?
같은 순간에 진행되는 두 수업은 겹치므로, 성립하는 시간표는 한 순간에 많아야 한 수업만 쓸 수 있다.
🧱일대일 대응여기 있는 것 하나가 저기 있는 것 하나와 딱 짝지어지면 두 무리의 크기는 같다.
7STEP 7
네 과목을 만드는 또 하나의 방법 살펴보기
그래서 가장 많이 듣는 것은 4과목입니다.
네 과목이 되는 다른 방법을 하나 더 찾아 두면, 네 과목이 고른 순서 때문에 우연히 나온 수가 아니라 진짜 천장이라는 것을 확인하는 셈이 됩니다.
4.OA.A.3Make A Systematic List정답
4 과목
4 + 2 + 2 + 1 = 9
답은 강좌의 개수이므로 1과 9 사이의 자연수여야 하고, 4는 그 안에 들어갑니다. 크기를 대충 어림해 봐도 말이 됩니다. 고른 네 강좌는 3 + 2 + 3 + 2 = 10시간을 쓰는데, 6시부터 20시까지가 14시간이니 꽉 차긴 해도 있을 법한 하루입니다. 반면 다섯 과목이라면 가장 짧은 강좌들만 모아도 2 + 2 + 3 + 3 + 3 = 13시간이 필요한데, 그 다섯 중 심리치료, 키 성장 체조, 언어발달은 모두 같은 오전 시간대에 몰려 있어서 겹치지 않게 끼워 넣는 일 자체가 불가능합니다. 답의 두 부분도 서로 맞아떨어집니다. 네 과목짜리 시간표를 실제로 보였고, 9시 30분, 11시 30분, 15시 30분, 19시라는 네 시각이 아홉 강좌를 모두 붙잡아 개수를 넷으로 묶어 주었습니다.
핵심 정리
가장 일찍 끝나는 강좌부터 붙잡으세요. 그리고 더 많이 들을 수 없다는 것까지 보이려면, 모든 강좌가 진행 중인 시각 몇 개를 찾아내면 됩니다.
- 아홉 강좌를 하나의 시간 띠 위에 그리기
- 끝나는 시각 순서로 시간표를 다시 정리하기
- 가장 일찍 끝나는 강좌부터 이어 붙이기
- 네 과목이 정말 겹치지 않는지 확인하기
- 아홉 강좌를 모두 붙잡는 네 시각 고르기
- 시각의 개수로 답을 네 과목까지 묶어 두기
- 네 과목을 만드는 또 하나의 방법 살펴보기
이어서 풀어볼까요