2019년 정보올림피아드 필기 중등부(11 ~ 2 - 3)

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

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

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

 

11번

3, 4, 5, 6각형의 모든 쌍을 만드는 문제 입니다. 모든 쌍을 생각하면 총 6가지 입니다.

4C2 = 4 * 3 / 2 = 6

이것을 표현하면 다음과 같습니다.

(3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)

모든 쌍이 가능한 경우를 생각해 최소의 수를 찾아야 합니다.

(3, 4)의 경우 최소 수는 7개 입니다. 그 다음 가능한 수는 정삼각형을 6개로 만들어 10개로 만들 수 있습니다. 정사각형을 8개로 만든다면 정삼각형 3과 앞의 8개로 11개만 있으면 만들 수 있습니다. 그 다음은 10 + 3, 10 + 4, 11 + 4로 13, 14, 15가 됩니다. 이렇게 3개 연속된 값이 있기 때문에 13이후 모든 수가 가능합니다.

(3, 5)는 최소 8부터 3, 5를 더해 11, 13개가 됩니다. 다음은 14, 16, 18개가 됩니다. 다음은 17, 19, 21, 23이 됩니다. 16, 17, 18, 19가 연속적으로 되어 있기 때문에 어떤수를 더해도 이후는 만들 수 있습니다.

위에서 11개로는 정삼각형과 정육각형을 만들 수 없다고 했습니다. (3, 6)이 가능한 최소의 수는 정삼각형 3개, 정육각형 6개로 9개가 최소 입니다. 삼각형, 육각형 모두 3의 배수이기 때문에 결국 9개 이상의 3의 배수일 때 만들 수 있습니다.

(4, 6)의 경우 처음 10개, 그 다음 14개가 됩니다. 그 이후 2의 배수로 만들 수 있습니다.

3의 배수, 2의 배수가 되려면 결국 14 이상의 6의 배수가 가능한 숫자 입니다.

(5, 6)은 최소 11개부터 5 * 2 + 6으로 16개, 5 + 6 * 2 로 17개가 가능합니다. 그 이후는 21, 22, 23개가 가능 합니다. 앞의 것에 5개, 6개씩 늘려보면 26, 27, 28, 29개가 가능합니다. 그 다음은 31, 32, 33, 34, 35개가 가능합니다. 이렇게 5개가 넘는 순간 모든 수가 가능합니다.

31 이상의 6의 배수가 되는 최소 수는 36이라는 것을 알 수 있습니다.

12번

2019년 초등부 12번과 같은 문제 입니다. 아래 링크의 12번 확인 바랍니다.

2024.03.16 - [알고리즘 설명] - 2019년 정보올림피아드 필기 초등부(11~2 - 3)

2019년 정보올림피아드 필기 초등부(11~2 - 3)

2 - 1번

2019년 초등부 2 - 1번과 같은 문제 입니다. 위 링크의 2 - 1번 확인 바랍니다.

 

2 - 2번

2019년 초등부 2 - 4번과 같은 문제 입니다. 아래 링크의 2 - 4번 확인 바랍니다.

2024.03.17 - [알고리즘 설명] - 2019년 정보올림피아드 필기 초등부(2-4~2-8)

2019년 정보올림피아드 필기 초등부(2-4~2-8)

 

2 - 3번

연속적으로 빵을 구매했을 때 좋아하는 정도가 최대가 되려면 최대한 많은 빵을 선택해야 합니다. 하지만 선호도가 음수인 경우도 있어 선호도의 합이 작아지는 부분을 찾아야 합니다. 먼저 가장 선호도가 높은 빵을 시작으로 빵을 골라보겠습니다.

처음에는 선호도가 높은 5를 선택합니다. 시계방향으로 이동하며 합계가 커지는지 작아지는지 확인합니다. 5 다음은 -2로 합계가 3이 됩니다. 선호도가 줄긴 했지만 다음 빵의 선호도가 4로 전체 선호도가 7이되어 이전보다 선호도가 커진것을 알 수 있습니다. 이렇게 계속 더해나가면서 선호도가 언제까지 늘게 되는지 확인 합니다.

선호도	5	-2	4	-1	2	-2	4	-1	3	0	1	-2
합계	5	3	7	6	8	6	10	9	12	12	13	11

빵을 선택하면 할수록 음수로 인해 일시적인 하락은 있지만 전체적으로 선호도의 합계가 커지는 것을 확인할 수 있습니다. 마지막 -2를 선택할 때까지 계속 숫자가 커집니다. 따라서 -2 하나를 제외한 모든 빵을 구매했을 때 선호도의 합이 최대가 됩니다.