[그래프][시도x] CHILDRENDAY 어린이날

1. 문제

 

C개의 선물들을

 

n명의 아이들에게 나누어주는데

 

m명의 아이들에게는 1+ g 개 

 

n-m 명의 아이들에게는 g개 씩 나누어준다고한다.

 

이때 C는 D 목록에 있는 수로만 이루어져있는 자연수여야한다.

 

 

 

2. C의 성질

 

이 문제는 D목록을 정점으로하는 무향 그래프를 생성하여

 

0에서부터(impossible)

 

bfs로 차근차근 하나씩 자리수를 늘려가며 맞아 떨어지는지 검사하는 문제인것같다

 

 

문제에서 주어지는 변수들로

 

수학식을 정리해보면 다음과 같다

 

C = m(1+g) + (n-m)g

C = ng + m

 

C%n = m%n  (C>=n)

C%n = m ,,, m>n

 

즉 목록 D로 구성되어있는 C를 n으로 나눈 나머지는

m을 n으로 나눈 나머지와 같아야한다

 

이때 m과 n은 고정점이므로 이점을 이용하면 목록이 주어졌을때 아마 impossible인지 확인할 수 있을 것이다.

 

(d1%n     d2%n     d3%n   ...)

 

 

한 자리 수 를 늘려가면서 나머지를 한번 비교해보자

 

c1: c1 mod n = a

 

c1c2 mod n =  ((c1 mod n) * 10 + c2) mod n = (c1 * 10 + c2) mod n

 

c1c2c3 mod n  = ((c1c2 mod n)* 10 + c3) mod n = (c1c2*10 + c3) mod n

 

 

이렇게 C를 몰라도 자릿수를 늘려가면서 나머지를 구할 수 있다.

 

하지만 이를 가지고 어떻게 그래프를 표현할지는 막막해 보인다.

 

책에서는 n으로 나눈 나머지를 정점으로 등호를 간선으로 표현하였다.

 

 

 

3. 책의 풀이: 나머지의 그래프 모델링

 

이 문제를 해결하려면 3가지 조건을 만족하는 c를 찾아야한다

 

1, n + m 이상이면서 최소

2. n으로 나눈 나머지가 m

3. d에 포함되어있어야함

 

 

책에서는 c를 n으로 나눈 나머지를 정점으로 표현한 방향 그래프를 만들었다.

 

따라서 그래프에는 0 부터 n-1 까지의 나머지를 표현하는 n 개의 정점이 있게 된다.

 

정점 a는 현재까지 만든 c를 n으로 나눈 나머지가 a인 상태를 나타낸다.

 

 

c의 뒤에 숫자 x를 붙이면 나머지는 (a*10 + x) mod n으로 바뀌게 된다.

 

따라서 이 두 정점을 간선으로 연결하되, 이 간선을 x로 번호를 매긴다.

 

 

이러한 그래프 상에서 0 에서 m으로 가는 최단 경로를 구하는 것이다.

 

 

4. 사전순으로 가장 작은 경로

 

그래프 모델링에의해 그래프를 생성하고 난뒤 

 

0에서부터 경로를 따라서 m까지갈때 최소인 경로를 찾아야한다. (사전순으로 가장 작은 경로)

 

이는 그래프를 만들 때 d의 목록에서 작은것부터 붙이면 해결된다.

 

 

 

증명은 다음과 같다

너비 우선 탐색은 항상 시작점을 먼저 방문한다   이때 시작점에서 가장 가까운 깊이가 1 인 H1에 속한 정점들은 항상 사용한 간선의 번호가 가장 작은 것 부터 큐에 추가된다.   시작점과 두 개 이상의 간선으로 연결된 정점 또한 마찬가지다, 항상 스패닝 트리에 작은 것 부터 추가된다.   H2에 속하는 정점들을 방문하면   시작점에서 H2에 속한 정점으로 가는 경로는 간선 두 개로 구성되어있다.   이 간선 또한 H1에서 간선의 번호가 증가하는 순서로 큐에 추가된것이다.   따라서 길이 2 인 경로들은 사전순으로 작은 것부터 검사되며 최단 경로가 두개 이상인 것 또한 항상 사전순으로 가장 작은것부터 발견된다. 이로인해 H2 에 속하는 정점 모두 사전순으로 큐에 추가된다, => 수학적 귀납법을 적용하면 그래프의 모든 정점에 대해 사전순으로 가장 작은 최단 경로가 찾아진다. 시작점으로 부터의 최단 거리가 같은 정점들은 최단 경로의 사전순으로 방문된다.

 

5. n+m 이상인 C 구하기

 

나머지가 m인 경로를 찾았다고 해도 항상 n+m이기 때문에

 

만약 그 이하이면 특정 경로를 돌아서 다시 m으로 가야한다.

 

이를 해결하려면 

 

n으로 나눈 나머지마다 두개의 정점을 만들어서 

 

정점 하나는 지금까지 만든 수가 n 미만일경우를 나타내고 

 

다른 하나는 지금까지 만든 수가 n 이상인 경우를 나타내는 것이다.

 

이로인해 n+m인 수 까지 다리를 이어 갈 수 있는것이다.

 

 

 

 

 

 

 

 

-알고리즘 문제해결전략 896p

CHILDRENDAY