BOJ 3026 V
* BOJ 3026 V
[분류 : 다이나믹/ 가지치기]
[풀이]
컷팅이 중요한 문제.
1. X가 10^5보다 크거나 같은 경우
A=1, B=10^11인 최악의 경우에서 X의 배수를 구할 때 10^6의 연산수가 필요해요. 이 경우엔 충분히 브루트포스로 계산이 가능합니다.
2. X가 10^5보다 작은 경우
최악의 경우를 생각해봅시다. X = 1, A = 1, B = 10^11이라면 브루트포스로 최대 10^11번을 계산해야하기 때문에 시간초과가 날 것임이 자명합니다.
[다이나믹]
자리수로 생각해봅시다. 수가 최대 10^11이므로 12자리가 자리수 최대가 됩니다.
관찰포인트는 인접한 자리수 간의 관계입니다. X=151이고 현재 10^3의 자리수를 구해야한다고 해봅시다. 이 때 1의 자리, 10의 자리 그리고 10^2자리에 어떤 숫자가 존재했을지 모르겠으나 X로 나눈 나머지가 76이라고 해봅시다. 그러면 현재 10^3의 자리수에 어떤 숫자를 넣느냐에 따라 이 나머지 값이 고정됩니다.
10^3에 넣을 숫자 |
10^3까지 숫자를 정한 수를 X로 나눈 나머지 |
0 |
(0 * 1000 + 76)%X = 76 |
1 |
(1 * 1000 + 76)%X = 19 |
2 |
(2 * 1000 + 76)%X = 113 |
3 |
(3 * 1000 + 76)%X = 56 |
4 |
(4 * 1000 + 76)%X = 150 |
5 |
(5 * 1000 + 76)%X = 93 |
6 |
(6 * 1000 + 76)%X = 36 |
7 |
(7 * 1000 + 76)%X = 130 |
8 |
(8 * 1000 + 76)%X = 73 |
9 |
(9 * 1000 + 76)%X = 16 |
이렇게 이전에 어떤 나머지를 가지고 있었는지를 가지고 현재 자리수에 어떤 수를 넣을 것인지 정하여 나머지 계산이 가능합니다. 따라서 함수의 프로토타입을 아래처럼 정의해봅시다.
: A보다 작은 수 중에 position 자리수를 가지는 수 중에서 나머지가 remain인 것의 개수
여기서 데이터가 부족합니다. 함수에 A보다 작아야함을 나타낼 수 있는 의미를 가지는 인자가 필요합니다. 이 인자에 따라 현재 자리수에서 고를 수 있는 수는 제한될겁니다. -> limit 변수
또한 입력 데이터에서 0을 사용할 수 없더라도 position에서 0을 사용할 수 있는 경우가 있습니다. 그건 바로 A보다 낮은 자리수를 갖는 수인 경우에 해당합니다. 가령 A=4231이라면 A보다 아래 있는 수 중 하나는 333으로 가져올 수 있습니다. 이는 10^3의 자리수에 0을 넣은 것이라고 볼 수 있습니다. 따라서 앞에서 수를 구성했는지 안했는지를 나타내는 플래그가 필요합니다 -> used 변수
아래처럼 프로토타입을 완성할 수 있습니다.
이 구조는 현재 내가 remain이란 나머지가 필요한데, 현재 position에서 k를 선택하면 k * 10^position을 덧셈하는 꼴이니 다음 재귀에선 (remain - k * 10^position + X) % X이란 나머지를 필요로 한다는 구조입니다. 결국 똑같은 문제를 계속 풀어야하니 다이나믹 프로그래밍인 것이죠.