2011년도 정보올림피아드 초등 시도예선문제 7번 풀이

다음을 모두 만족하는 가장 작은 양의 정수를 7로 나눈 나머지는?

 - 2로 나누면 나머지가 1이다. 

 - 3으로 나누면 나머지가 1이다. 

 - 4로 나누면 나머지가 1이다.

 - 5로 나누면 나머지가 1이다

 - 6으로 나누면 나머지가 1이다

문제 풀이)

일반적으로 위와 같은 문제가 나오면 2,3,4,5,6 의 최소공배수 60 + 1 = 61 로 선택해서 나머지를 5로 선택하기 쉽다.

하지만 위의 조건을 만족하는 가장 작은 수는 숫자 1이다.

1을 7로 나눈 나머지는 1이다.

위와 유사한 문제로 다음과 같은 문제가 있을수 있다. 

 - 2로 나누면 나머지가 1이다. 

 - 3으로 나누면 나머지가 2이다. 

 - 4로 나누면 나머지가 3이다.

 - 5로 나누면 나머지가 4이다

 - 6으로 나누면 나머지가 5이다

이 경우는 2,3,4,5,6의 최소공배수 60 보다 1 작은 수 59를 선택하면 된다. 이때 7로 나눈 나머지는 3이 된다.

그러면 다음과 같은 문제는 어떻게 풀수 있을까?

- 3으로 나눈 나머지는 2이다.

- 5로 나눈 나머지는 4이다.

- 7로 나눈 나머지는 2이다.

이럴때는 나머지가 같은 3과 7의 최소공배수를 구한다. 21이다.

21의 배수 + 2 가 5로 나눈 나머지가 4가 되는 수가 되는 수가 가장 작은 수가 된다.

따라서 21 + 2 = 23, 21 * 2 + 2 =44 ( 여기서 5로 나눈 나머지가 4가 된다.)

위와 같은 유형의 나머지 정리는 네이버 지식백과의 나머지정리 (http://terms.naver.com/entry.nhn?docId=2039056&cid=47308&categoryId=47308) 를 참고하면 더 재미있는 이야기를 확인 할 수 있다.

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