[고등부] 2024 KOI 2차대회 대비 모의고사 (1주차)

기업가 정올이는 N개의 건물 청사진을 구상했다. 각 청사진은 두 정수 G와 R로 구성되어 있다.

• G: 로비의 높이. 이 수치는 0이 되는 것이 가능하며, 그 경우 로비가 없음을 의미한다.

• R: 거주층의 높이. 건물에는 최소 한 개 이상의 거주층이 존재한다.

정올이는 두 명의 후계자에게 N개의 청사진을 공평하게 분배하고 싶다.

각 후계자들은 자신에게 할당되는 청사진 하나 당 하나의 건물을 건설할 것이며, 다만 각 건물별로 거주층을 몇 층으로 할지 결정할 것이다.

여기서 공평한 분배란 두 후계자가 각자 건설한 빌딩들의 높이 합이 동일하게 지어질 수 있는 경우를 의미한다.

예를 들어 N=3의 아래와 같은 경우:

1. G=1, R=1 (빌딩의 높이가 2, 3, 4, ... 등이 될 수 있음)

2. G=0,R=3 (빌딩의 높이가 3, 6, 9, ... 등이 될 수 있음)

3. G=2, R=1 (빌딩의 높이가 3, 4, 5, ... 등이 될 수 있음)

첫 번째 후계자가 1번과 3번 청사진을 받고, 두 번째 후계자가 2번 청사진을 받았을 때, 첫 번째 후계자가 1번과 3번 청사진으로 둘 다 높이 3짜리 건물을 짓고, 두 번째 후계자가 2번 청사진으로 높이 6까지 건물을 짓는다면 두 후계자가 지은 건물의 높이의 합은 둘 다 6으로 공평하게 분배가 될 수 있다.

정올이를 도와 공평한 분배가 가능한지 판별하는 프로그램을 작성하시오.