창의적 문제해결 기말고사 문제
1. 가로등 색칠하기
어떤 마을에는 도로가 다음과 같이 트리형태로 구성되어 있다. 그리고 각 노드들 에는 가로등이 하나씩 배치되어 있다.
이와 같은 트리에서 검은색은 꺼진 가로등, 흰색은 켜진 가로등을 의미한다. 이 문제의 목적은 모든 가로등을 켜는 것이다. 모든 가로등에는 두 개의 버튼이 있다.
각 버튼의 동작은 다음과 같다.
- 버튼1 : 그 가로등의 상태가 바뀐다. 켜져 있으면 꺼지고 꺼져 있으면 켜진다.
- 버튼2 : 그 가로등과 연결되어 있는 모든 가로등의 상태가 변한다. (연결되어 있 는 가로등이란, 거리가 1인 모든 가로등을 의미한다.)
예를 들어 위 트리의 루트에 있는 가로등의 버튼 1을 누르면 다음과 같이 상태가 바뀐다. (트리의 윗부분만 볼 때)
만약 처음상태에서 버튼1이 아니라 버튼 2를 눌렀다면 상태는 다음과 같이 바뀐다.
이 마을의 모든 가로등을 켜기 위해서 눌러야할 버튼의 최소횟수를 구하고, 그 풀 이과정을 쓰시오.
2. 구름사다리
구름사다리
길동이는 요즘 구름 사다리 놀이를 하고 있다. 구름 사다리는 다음 그림과 같이 생겼다.
일반적인 구름사다리는 모든 손잡이가 지상으로부터 같은 높이에 있다. 하지만 길 동이가 하고자하는 구름사다리는 각 단의 높이가 서로 다를 수도 있다.
구름사다리의 손잡이 간의 이동은 서로 인접할 경우에 가능하며, 구름사다리의 높 이가 서로 다른 곳으로 이동하기 위해서는 두 구름사다리 손잡이 높이의 차만큼의 힘이 있어야 한다.
예를 들어 높이가 4인 손잡이에서 7인 손잡이로 이동하려면 적어도 체력이 3이상 은 되어야 한다.
만약 길동이의 체력이 2이고 각 구름사다리 손잡이는 10개이며 각 손잡이의 높이가 [ 2 5 3 4 6 5 7 4 5 3 ]
라면, 길동이는 2번째 손잡이에서 출발하여 구간 [ 5 – 3 – 4 – 6 – 5 – 7 ] 의 6개의 손잡이를 이용할 수 있으며, 8번째 손잡이에서 출발하면 구간 [ 4 – 5 – 3 ] 의 3개의 손잡이를 이용할 수 있다.
구름사다리의 손잡이 수가 10개이고 각 높이가 다음과 같다.
[ 255 155 197 188 234 264 268 281 152 200 ]
길동이의 체력이 97일 때, 길동이가 이용할 수 있는 최대 구간의 크기와 시작 칸 과 끝 칸의 번호를 쓰시오. (단, 가장 왼쪽의 번호가 1번이고 가장 오른쪽 칸의 번 호는 10번이다.)
3. 새로운 광물
우주 탐사를 갔던 CSP호가 각 행성에서 지구상에서는 존재하지 않는 새로운 광 물을 10개 채취해왔다. 이 10개의 광물들에 대해서 각각 ∼까지 일련번호를 부여했다. CSP연구소에서는 각 광물들의 안정성이 모두 다르다는 사실을 발견했다.
그래서 이 안정성을 기준으로 안정성 번호를 부여하고자 한다. 이 번호가 작을수록 더 안정적이다.
이 10개의 광물들의 안정성을 분석하기 위해서 특별한 분석장비를 이용한다. 이 분석장비는 두 광물에 대해서 어느 것이 더 안정적인지를 구할 수는 있지만 절대적 인 수치로 값을 구할 수 는 없다. 그리고 이 장비를 한 번 이용할 때 매우 많은 비용이 들기 때문에 이 장비를 쓰는 횟수를 최소화하고자 한다.
지금까지 11번 장비를 이용하여 구해둔 결과는 다음과 같이 주어져있다. 어떠한 경우에도 모든 광물들의 안정성을 정확하게 분석하기 위해서는 이 분석 장비를 최 소 몇 번을 더 써야하는지를 구하고, 그 풀이과정을 서술하시오.
<이미 구해 둔 값>
4. 3을 보는 시간
시, 분, 초를 표시하는 위와 같은 시계가 있습니다.
이 시계는 하루를 00:00:00 ~ 23:59:59 까지 표시합니다.
하루 동안 숫자 ‘3’을 볼 수 있는 시간은 몇 초입니까?
같은 시간에 여러 개의 ‘3’을 볼 수 있어도 1초로 계산합니다.
예를 들어 13:33:33을 볼 수 있는 시간은 1초입니다.
