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

2019년 정보 올림피아드 1차 중등부 풀이 입니다.

1번

숫자를 하나하나 계산하기 힘든 문제 입니다. 하지만 잘 보면 숫자를 다른 형태로 바꿀 수 있을 것 같습니다.

(2020 - 1) * (2020 + 1)

위와 같이 바꿔주겠습니다. 이 것은 결국 아래와 같게 됩니다

2020 ** 2 - 1

2020을 제곱한 숫자에 1을 뺀 숫자를 찾고, 2진수로 표현했을 때 연속된 1의 개수를 찾는 문제 입니다. 즉 우리는 정확한 숫자 계산을 할 필요가 없습니다.

결국 이 문제는 2020을 제곱한 숫자의 2진수에 오른쪽 연속된 0이 몇개 있는지 묻는 문제 입니다. 예를 들어 10100000 이라는 2진수가 있습니다. 오른쪽에서 보면 0이 총 5개가 있음을 알 수 있습니다. 여기에 1을 빼면 10011111가 되고 1의 개수 역시 5개가 됩니다.

이렇게 2020 ** 2의 2진수에는 0이 몇개 있는지 찾으면 1을 뺐을 때 1의 개수와 같은 것 입니다. 10진수는 그 숫자에 들어 있는 10의 개수만큼 0이 생깁니다. 10의 배수가 아닌 어떤수 a가 있을 때 (a * 10) ** 5은 0이 5개 있음을 알 수 있습니다. 2진수는 2의 제곱수 만큼 0이 있는 것과 같습니다.

2020은 101 * 5 * (2 ** 2) 입니다. 이 전체의 수를 제곱한다면 다른 수를 제외하고 2만 확인해 보면 2 ** 4 가 됩니다. 즉 2020 ** 2는 2진수로 변환 했을 때 오른쪽에 연속된 0이 4개 있는 수 입니다. 여기에 1을 빼면 연속된 4개의 0은 1이 되게 됩니다.

즉 연속된 1의 개수는 4개가 됩니다.

2번

3부터 15의 합을 계산하기 쉽지 않습니다. 1부터 15까지의 합을 구한 다음 1부터 2까지의 합인 3을 빼는 것이 더 쉽습니다. 1부터 15까지의 합은 15 * (15 + 1) / 2 으로 120이 됩니다.

저 식을 이해하기 위해 1부터 15까지 합을 구하는 방법은 다음과 같습니다. 1부터 15까지 일렬로 늘어서 있는 모습을 생각합니다. 그리고 그 밑에는 15부터 1까지 일렬로 늘어서 있는 것을 생각해 보겠습니다.

아래 위 숫자의 합은 모두 16임을 알 수 있습니다. 1부터 15까지의 합을 구하는 것이기 때문에 16의 개수는 총 15개 있습니다. 이것은 15 * 16으로 구할 수 있습니다. 그런데 한 가지 문제가 있습니다. 우리는 1부터 15까지의 합을 구하려 했는데 15부터 1까지의 합을 또 더해주었습니다. 즉 우리가 구하려는 값의 2배가 된 것이 15 * 16 입니다. 그러니 2로 나누어 주어야 1부터 15까지의 합계를 구할 수 있습니다. 이것을 식으로 나타내면 1부터 어떤 수 a까지의 합계는 다음과 같습니다.

a * (a + 1) / 2

1부터 15까지의 합계는 120이라는 사실을 알았습니다. 이 문제는 1부터가 아닌 3부터의 합계를 구해야 합니다. 그렇기 때문에 120에서 숫자 1, 2를 빼면 117이 됩니다.

3부터 15까지의 합계는 117이고, 여기에 어떤 수를 뺀 합계가 106이라고 합니다. 117에서 106을 빼면 11이 남고, 우리는 빠진 어떤 수가 11이라는 사실을 알 수 있습니다.

3번

20진수를 사용하기 위해 위에서 알고 싶은 숫자를 확인해 보면 각각 16과 13입니다. 저 두 수를 통해 20진수로 바꾼다면 16 * 20 + 13 과 같습니다. 16 * 20은 320이고 여기에 13을 더하면 333이 됩니다.

4번

어린이는 2명 이하, 어른은 1명밖에 건널 수 없습니다. 따라서 어른 한 명을 이동시키기 위해 몇 번의 이동이 필요한지 알 수 있게 되면 모든 군인이 강을 이동하는데 걸리는 왕복하는 횟수를 알 수 있습니다.

먼저 아이 두명이 강을 건너갑니다. 한 번의 이동이 생깁니다.

한 아이를 남겨두고 나머지 한 아이가 배를 타고 돌아 옵니다. 이제 두 번의 이동이 생겼습니다.

이제 아이를 두고 어른이 배를 타고 이동 합니다. 여기까지 배의 이동은 세 번 입니다.

어른을 놔두고 아이가 배를 타고 처음 위치로 이동합니다. 아이는 처음 위치로 모두 이동하였습니다. 이제 총 4번의 이동을 하였고, 어른 한 명을 옮기게 되었습니다.

이렇게 어른 한 명을 이동하는 데 4번의 강을 건넜습니다. 그렇기 때문에 어른 20명을 이동시키기 위해서는 총 80번의 이동이 필요합니다.

5번

M월 D일이라고 하면 어렵기 때문에 1월 1일 월요일이라 생각하고 문제를 해결해 보겠습니다. 1년 뒤 1월 1일은 365일 뒤 입니다. 365를 7로 나누면 52주가 되고 나머지가 1이 됩니다. 즉 1일이 추가되어 화요일이 된다는 것을 알 수 있습니다.

400년 뒤라면 400일이 추가 됩니다. 여기에 윤년이 더해지게 됩니다. 윤년은 4년 마다 1일씩 늘어납니다. 그리고 100의 배수는 늘어나지 않고, 400의 배수에서 다시 늘어납니다. 먼저 4년마다 늘어나는 1일은 400년동안 총 100번 있습니다. 100년 마다 윤년이 되지 않는 해가 돌아오기 때문에 4일이 빠집니다. 마지막으로 400년은 1일이 늘어나기 때문에 1일이 더해집니다. 100 - 4 + 1이 되어 97일이 됩니다. 그럼 총 늘어나는 날짜는 497일이 됩니다. 이 값을 7로 나누면 71이 되고, 나머지가 없기 때문에 요일의 변화가 없습니다. 따라서 월요일이 됩니다.