2019년 정보올림피아드 필기 중등부(6 ~ 10)

2019년 정보올림피아드 중등부 문제 풀이 입니다. 이전 문제는 아래 링크 확인 바랍니다.

2024.03.18 - [알고리즘 설명] - 2019년 정보올림피아드 필기 중등부(1 ~ 5)

2019년 정보올림피아드 필기 중등부(1 ~ 5)

6번

한 붓 그리기 관련 내용은 아래 링크 확인 바랍니다.

2024.03.15 - [알고리즘 설명] - 한 붓 그리기 가능한 경우

한 붓 그리기 가능한 경우

홀수의 차수가 2개보다 큰 경우 한 붓 그리기를 할 수 없습니다. 홀수점은 홀수개 있을 수 없기 때문에 2개 다음은 4개의 홀수점을 가지는 경우 입니다. 이 경우에 한 붓 그리기는 불가능 하지만 두 붓 그리기가 가능합니다.

위 그림이 홀수점이 4개로 두 붓 그리기가 가능한 것을 알 수 있습니다. 따라서 이 도형이 두 붓 그리기가 가능한 도형 입니다.

참고로 홀수점이 6개가 되면 세 붓 그리기가 가능합니다.

7번

위상 정렬을 수행하는 문제 입니다. 위상 정렬을 잘 모른다면 아래 링크를 확인 바랍니다.

https://wikidocs.net/206817

03. 위상 정렬

아래 링크처럼 작업이 있을 때 시간을 알기 위해서는 하나하나 해봐도 알 수 있습니다. 하지만 위상 정렬을 알고 있기 때문에 위상정렬로 문제를 해결해 보겠습니다.

위와 같이 되어 있을 때 차수가 0인 항목을 지워나가며 몇 번만에 모든 과정을 완료하는지 알아보겠습니다. 두 명이 작업을 하고 있기 때문에 차수가 0인 두 항목을 지워나가 보겠습니다.

1, 2번을 수행해 1시간이 지났습니다. 이제 다시 차수가 0인 항목을 지워 줍니다.

3, 4번을 수행하여 2시간이 지났습니다. 차수가 0인 항목을 지워나가겠습니다.

5, 6 번을 수행하였고, 3시간이 지났습니다. 이렇게 7, 8번을 지우면 4시간, 9, 10번을 지우면 5시간이 지나게 됩니다.

6시간째에 2명의 장인이 있지만 수행 가능한 작업은 하나밖에 없습니다. 따라서 한명의 장인은 쉬고, 한명으로 11번 작업을 진행하게 됩니다. 그리고 마지막 7시간째에 12번 작업을 진행하면서 모든 작업을 완료하게 됩니다.

정답은 총 7시간이 됩니다.

8번

규칙 1과 규칙2는 기존 하노이탑과 같은 규칙 입니다. 여기에 규칙 3이 추가되어 있습니다. 규칙 3은 원판을 한 개 혹은 두 개를 옮길 수 있다고 합니다. 한 개를 옮기는 것보다 두 개를 옮기는 것이 무조건 이득이기 때문에 두 개씩 옮기면 최소값을 구할 수 있습니다.

총 7개의 원판이기 때문에 두 개씩 이동하면 위에서부터 6개 까지는 두 개씩 옮기고, 마지막 한 개는 남는것이 없기 때문에 한 개 이동합니다. 그럼 총 4개의 원판을 옮기는 경우와 같습니다.

하노이 탑 이동 순서에 맞게 4개의 원판을 이동시키면 총 15번의 이동으로 다른 기둥으로 옮길 수 있습니다.

9번

9글자의 회문을 만들어야 합니다. 하나하나 회문을 찾으려 한다면 굉장히 어려울 수 있습니다. 하지만 9글자를 반으로 나누어 5글자라고 한다면 문제를 좀 더 쉽게 만들 수 있습니다.

위 그림과 같이 5글자로 문장을 만들고, 나머지 4글자로 회문을 만들면 9글자의 회문이 되는 것입니다.

먼저 1번 위치에 a일 때 몇 번째인지 확인해 보겠습니다. 2부터 5까지 a, b, c가 들어갈 수 있습니다. 4개의 위치에 3개의 문자를 넣을 수 있기 때문에 총 3 * 3 * 3 * 3으로 총 81번째가 됩니다.

81번째 이후는 1번 위치가 b가 됩니다. a일 때와 마찬가지로 81번의 경우가 있습니다. a일 때 81번, b일 때 81번으로 총 162번째 까지를 지나가게 됩니다. 따라서 첫 번째 문자는 c가 됩니다.

다음으로 1, 2번 위치가 ca가 되는 경우를 생각해 보겠습니다. 3, 4, 5 위치에 3가지 경우이기 때문에 27번의 경우가 지나가게 됩니다. 앞에서 구한 162 + 27로 189가 됩니다. 이제 cb가 시작하여 11번째 위치를 찾으면 됩니다.

cba에서 4, 5번을 생각하면 9가지 경우가 있습니다. 189 + 9로 198번째까지 찾았습니다. cbb로 시작하고 2번째를 찾으면 그것이 정답입니다.

cbbaa 가 199번째이고, cbbab가 200번째 입니다. 200번째를 찾았기 때문에 5글자가 아닌 9글자인 회문으로 만들어 주면 cbbababbc가 됩니다.

10번

이 문제는 기초적인 DP 문제 입니다. 피보나치 수열과 같은 문제로 하나하나 모든 경우를 찾기는 힘듭니다. 하지만 피보나치 수열처럼 계산을 하면 쉽게 문제를 해결할 수 있습니다.

먼저 길이가 1인 경우는 1가지 경우 입니다.

다음으로 길이가 2인 경우는 앞의 경우에 세로로 하나 더 추가하거나, 두 개를 놓는 경우 2가지가 있습니다.

길이가 3개인 경우는 길이가 1인 경우에 누워있는 두 개를 추가하거나, 길이가 2인 경우에 세로로 한개를 추가하는 것 입니다.

길이가 4개인 경우는 길이가 2개인 경우에 누워있는 두 개를 추가하거나, 길이가 3개인 경우에 세로로 하나 추가하는 것입니다.

즉 우리는 이것이 피보나치 수열과 똑같다는 것을 알 수 있습니다.

F(n) = F(n - 1) + F(n - 2)

의 식으로 나타낼 수 있고, F(10)을 구하면 됩니다. F(1)부터 F(10)까지 구해보겠습니다.

1	2	3	4	5	6	7	8	9	10
1	2	3	5	8	13	21	34	55	89

F(10)은 89이고 정답은 89가 됩니다.