조건을 만족하는 시간표, 하나만 가능할까?

1. 정해야 할 것과 지켜야 할 것 나누기

우선 A·B·C가 각각 언제 시작하는지 정해야 합니다. 선택할 수 있는 시각은 10시·11시·12시입니다. 여기에 조건 세 가지를 적용합니다. ① A는 10시에 시작할 수 없다. ② B는 A보다 먼저 시작한다. ③ C는 12시에 시작할 수 없다. ‘먼저’는 두 시작 시각의 순서를 비교하는 말이며, 반드시 바로 앞 시간이라는 뜻까지 포함하지는 않습니다.

조건 만족 문제에서는 선택할 대상, 가능한 값, 지켜야 할 관계를 구분합니다. 하버드 CS50 AI 공개 강의의 해당 절에서도 이 세 요소를 설명합니다. 이 활동은 그 기본 개념을 익히는 소규모 전수 검사입니다. 강의의 예제나 알고리즘을 그대로 재현한 활동은 아닙니다.

참고: Harvard CS50 AI · Brian Yu, David J. Malan · Lecture 3: Optimization · Constraint Satisfaction

2. 여섯 배치를 빠짐없이 적기

10시에 올 모임은 셋 중 하나입니다. 그 모임을 정하면 11시에는 남은 둘 중 하나가 오고, 12시에는 마지막 모임이 옵니다. 따라서 중복 없는 배치는 3×2×1, 모두 여섯 가지입니다. 표의 한 행은 10시부터 12시까지의 순서입니다. A와 B를 동시에 10시에 넣는 경우는 ‘한 시간대에 한 모임’이라는 기본 설정에서 이미 제외됩니다.

처음부터 마음에 드는 답 하나를 고르지 말고, 각 배치를 조건과 대조해 보세요. A로 시작하는 두 행은 조건 ①에서 제외됩니다. B·A·C는 C가 12시에 오므로 조건 ③에 어긋납니다. C·A·B는 B가 A 뒤에 오므로 조건 ②에 어긋납니다. 남는 것은 B·C·A와 C·B·A 두 가지입니다.

3. 조건을 하나 더하면 무엇이 달라질까?

조건 ④ ‘C는 B보다 나중에 시작한다’를 추가해 봅시다. 남아 있던 B·C·A에서는 B가 10시, C가 11시여서 새 조건이 맞습니다. C·B·A에서는 C가 먼저이므로 맞지 않습니다. 따라서 네 조건을 모두 적용하면 B·C·A만 남습니다. ‘가능한 배치가 있다’에서 ‘가능한 배치는 하나다’로 결론이 강해진 셈입니다.

어떤 조건이 겹치는 역할을 하는지도 살펴볼 수 있습니다. 조건 ②는 B가 A보다 먼저 와야 한다고 정합니다. 이 조건만으로도 A가 첫 시간인 10시에 올 수 없으므로 조건 ①은 이미 충족됩니다. 네 조건을 켠 상태에서 조건 ①만 꺼도 답은 그대로 하나입니다. 조건이 여럿 적혀 있어도 모두 독립적으로 답을 좁히는 것은 아닙니다.

4. 검사 결과를 설명으로 바꾸기

버튼을 눌러 답이 나왔다는 사실만으로 풀이가 끝나지는 않습니다. 자신이 켠 조건을 말하고, 살아남은 배치가 각각의 조건을 만족하는 이유를 설명해 보세요. 답이 하나라고 주장하려면 나머지 후보가 모두 제외된 이유도 필요합니다. 이 문제에서는 여섯 배치를 빠짐없이 열거했으므로 그 범위에서 유일성을 확인할 수 있습니다.

모임과 시간대가 많아지면 전체 배치 수가 빠르게 늘어납니다. 현실의 시간표에는 휴식, 장비, 이동 시간 같은 조건도 들어갑니다. 이 작은 표에서 성공했다고 모든 시간표를 같은 속도로 해결할 수 있는 것은 아닙니다. 여기서 익힐 것은 조건을 분명하게 표현하고, 가능한 답의 수를 근거와 함께 설명하는 습관입니다.