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

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 이후의 모든 갯수는 작은구슬과 중간구슬의 조합으로 바꿀수 있습니다.

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