퀴즈 412 사탕 나누기

---

나는 x 개의 사탕을 가지고 있다.

이 사탕은 3개를 한 묶음으로 나눌 때 사탕 1개가 남으며

4개, 5개, 6개를 한 묶음으로 나눌 때 역시 사탕 1개씩이 남았다.

하지만 7개씩 묶었더니 남는 사탕이 없었다.

내가 가지고 있는 사탕의 최소 개수는 몇개인가?

풀이

x-1 은 3,4,5,6 의 배수이기에 3,4,5,6 의 최소 공배수인 60의 배수가 될 것이다.

x= 60k+1 이 중에서 7의 배수가 되는 가장 작은 수를 찾으면 된다.

그래서 답은 301

퀴즈 414 사탕 나누기 2

---

나는 x 개의 사탕을 가지고 있다.

이 사탕은 2개를 한 묶음으로 나눌 때 사탕 1개가 남으며

3개를 한 묶음으로 나눌 때 2개가 남고

4개를 한 묶음으로 나눌 때에는 3개

5개일 때는 4개, 6개일 때에는 5개가 남았다.

하지만 7개씩 묶었더니 남는 사탕이 없었다.

내가 가지고 있는 사탕의 최소 개수는 몇개인가?

[이 문제 역시 충분히 일반화가 가능하다.

핵심은 N 개로 나누었을 때 나머지가 N-1 이 나왔다는 것,

이 규칙성을 잘 모르겠다면, 2개로 나누었을 때 나머지가 1, 3개로 나누었을 때 나머지가 2 가 되는 숫자[작은 경우] 를

먼저 생각해보자.]

풀이

해당 숫자는 2,3,4,5,6 의 최소공배수 인 60의 배수에 -1 인 숫자이다. [왜 이런 숫자가 되는지 알겠는가? 이런 숫자들의 일반적으로 구하는 방법에는 중국인의 나머지 정리를 쓰면 되지만, 최소공배수를 생각해도 쉽게 이 아이디어를 떠올릴 수 있다. 잘 안된다면 작은 숫자에서 시도를 해보라]

x=60k-1 이 중 7의 배수가 되는 최소의 수는 119 이다.

c.f)

참고로 412, 414 는 최소공배수, 최대공약수 개념을 이용해서 trial and error 혹은 중국인의 나머지 정리로 풀 수 있지만, 간단하게 프로그램을 만들어서 풀 수 도 있다. [이런 류의 문제가 초중고 프로그래밍 대회에 출제되곤 한다. For 와 IF 구절을 잘 쓰면 된다. ]

시간이 되면 예전처럼 여러 문제들을 코딩으로 풀어보는 시도를 해보고 싶다.