2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/정보영재

2017년 정보올림피아드 예선 중13번 문제 풀이

원당컴퓨터학원 2017. 8. 31. 12:18

2017년 정보올림피아드 중학교 예선 문제중에서  13번 문제를 풀어 보겠습니다.


문제는 다음과 같습니다.


 

철수와 영희는 구슬을 가지고 있다. 

철수는 작은 구슬과 중간 구슬을 가지고 있고 영희는 큰 구슬을 가지고 있다. 

구슬의 가치는 작은 구슬 9개가 큰 구슬 5개와 같으며, 중간 구슬 9개가 큰 구슬 8개와 같다. 

철수와 영희는 서로 같은 가치만큼 구슬을 바꾸려고 한다. 

구슬을 자를 수는 없으므로 철수는 작은 구슬 몇 개와 중간 구슬을 몇 개를 합쳐서 영희가 가진 큰 구슬 몇 개와 바꾸어야 한다. 

당연히 큰 구슬 1개를 바꿀 수 있는 방법은 없다. 

하지만 X개 이상의 큰 구슬에 대해서는 항상 바꿀 수 있는 방법이 있다.

이 때 X의 최솟값을 구하여라. (철수와 영희는 충분히 많은 수의 구슬을 가지고 있다고 가정하자.)

① 2 ② 3 ③ 4 ④ 27 ⑤ 28



정답은 3번 4개 입니다.


문제풀이는 다음과 같습니다.


작은 구슬 1개 = 5/9 큰 구슬

중간구슬 1개 = 8/9 큰 구슬

5/9 * s + 8/9 * m = L 

L=2k 인 경우(큰구슬이 짝수개 인경우)

5 * s + 8 * m = 18k <- 10k + 8k<- 짝수개의 큰 구슬 합은 작은 구슬과 큰 구슬의 합으로 표현할 수 있다.

s=2,m=1 인 경우 k=1 로 표현이 가능 따라서 2k 이므로 짝수는 모두 가능

예) 큰 구슬 2개 =  5/9 * 2 + 8/9 * 1 ( 작은 구슬2개 + 중간 구슬 1개)



L = 2k -1 일때 (홀수개 만들수 있는지 확인하기 위해서)

5 * s + 8 * m = 9 * (2k-1) = 18k – 9 = 18(k-1) + 9 = 18(k-2) + 27 = 18(k-3) + 45

45 는 5*1 + 8 * 5  k=3 일때 8과 5의 배수로 나타내짐

K=3 일때 L=5

예) 큰구슬 5개 = 5/9 * 9 + 8/9 * 0 또는 5/9 * 1 + 8/9 * 8(작은구슬 9개 또는 작은구슬 1개와 중간구슬 8개)

따라서 짝수 갯수는 모두 가능하고 홀수 개수는 5부터 가능하다. 

그러므로 4 이후의 모든 갯수는 작은구슬과 중간구슬의 조합으로 바꿀수 있습니다.


정보올림피아드 문제 풀이 리스트 정리





사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기