문제 파악
답이 될 수 있는 숫자를 구성하는 숫자가 정해져 있으므로, 답을 구성할 수 있는 숫자들을 그래프의 노드로 보고 BFS로 탐색하면서 최소가 되는 답을 찾을 수 있지 않을까 생각했다. 그러나 문제점은 이런 방식으로 탐색할 경우 답이 존재하지 않는 경우 종료하는 지점을 설정하는 것이 불가능 하다는 것이다.
문제 풀이
모듈로 연산
문제 풀이의 핵심적인 아이디어는 답이 되는 숫자는 어린이의 수 n으로 모듈로 연산을 했을 때의 값이 m인 숫자라는 것이다. 따라서 숫자 자체에 집중하기 보다는 나머지 값에만 초점을 맞춰도 답을 찾는 데 아무런 문제가 없다.
모듈로 연산은 나누기를 제외한 사칙 연산이 성립하므로 나머지 값만으로 노드를 구성하고 답을 구성하는 숫자인 d를 엣지로 보면 정답이 될 수 있는 노드인 m까지 가는 과정을 그래프로 나타낼 수 있다.
최소값
모듈로 연산을 통해 해당하는 노드를 찾았다고 하더라도 문제의 조건은 가장 작은 값을 찾는 것이다. 이 조건을 만족하기 위해서는 숫자의 배열이 사전 순으로 가장 작은 값이어야 한다. 이를 만족하기 위해서는 BFS 과정에서 가장 작은 값이 먼저 탐색 되게끔 하는 것이다. 그럼 우리가 찾는 노드를 가장 먼저 발견하는 엣지를 통해 만들어진 경로는 반드시 가장 작은 값이 된다.
노드 구분
마지막으로 추가해줘야 하는 조건은 만약 구한 답이 n+m보다 작은 경우 모든 어린이들에게 장난감을 한 개 이상 줄 수 없다. 따라서 이 조건을 충족하기 위해서노드를 두 종류로 구분해 준다. 경로를 통해 얻은 값이 n미만인 노드와 n이상인 노드로 구분하여 n미만인 노드는 정답으로 선택되지 않게끔 번호가 m인 노드에 도달하는 경로를 답으로 하는 것이 아니라 n+m인 노드를 답으로 한다.
이를 구현하기 위해서는 경로를 선택할 때 경로를 통해 만들어진 값이 n보다 작은 경우와 큰 경우를 구분해서 표현해주면 된다.
느낀점
- 답을 구하는 과정에서 나누는 과정이 필요한 경우 모듈로 연산을 통해 복잡하거나 큰 수를 더 작은 체계 안에서 나타낼 수 있다.
- 특정 조건을 만족해야 하는 경우 결과를 조건문에 넣어 답을 찾을 수도 있지만 연산 과정 중에 특별한 처리를 해주면 더 간단하게 만족시키는 경우가 있다.
- string을 정수로 바꿀 때 함수로 처리해 주는 것 보다 '0'을 빼주는 것이 간편하다.
