https://algospot.com/judge/problem/read/ZIMBABWE
난이도 : 어려웠다!!
풀이를 보고도 이해가 안됐는데, 총 4단계로 분류된 해설을 보고나니 좀 명확하게 이해가 되었다.
- 마지막에 계란 가격이 올랐을 때, 종욱이는 광고판에 꽂힌 플라스틱 판의 순서만 바꿨습니다. 다른 플라스틱 판을 가져오거나 있던 플라스틱 판을 뺄 일은 없었다는 것이죠.
- 마지막 계란 가격을 보면서 '와 이거면 정확히 사탕 m개를 살 수 있구나' 라고 생각했습니다. 따라서 마지막 계란 가격은 m의 배수였습니다. (사탕 가격도 이미 올랐기 때문에 이걸 가지고 계란 가격을 계산할 수는 없습니다)
풀이는 단순하게도 숫자배열 (ex [1,2,3,4])로 가능한 모든 조합 중, 현재 숫자 n보다 작고, m의 배열인 숫자 배열을 구하면 된다.
그러나 문제는 (1 <= e <= 10^14)이라 숫자 배열의 길이가 14자리이고, 2000ms 안에 통과해야하기 때문에 단순 dfs로 모든 배열을 구하거나, 다음 순열 구하기 같은 방식을 사용하면 터무니 없이 시간이 오래걸린다.
python의 permutation 라이브러리를 사용해도 마찬가지
때문에 핵심은 최대한 케이스를 줄이는 것.
한 단계씩 문제를 고도화하며 풀어보자.
1. 단순히 모든 숫자 배열 조합 구하기
def dfs(array, visit, d, newA):
if d == len(array) :
print(' '.join(map(str, newA)))
for i in range(len(array)):
if visit[i] : continue
newA[d] = array[i]
visit[i] = True
dfs(array, visit, d+1, newA)
visit[i] = False
array = [1,1,2,3]
visit = [False, False, False, False]
newA=[0,0,0,0]
dfs(array, visit, 0, newA)
dfs를 사용해 모든 숫자의 배열 조합을 구할 수 있었다.
그런데 문제는 1이 2번 들어있기 때문에, 똑같은 조합이 중복으로 나타난다.
2. 조합에서 중복을 제거하기
단순히 조합을 만든다음 해시에 저장해서 뺄 수도 있지만, 애초에 처음부터 중복이 될 것 같으면 연산을 피하는 방법이 있다.
이를 위해서는 다음 단계가 필요하다.
- 인자의
array가 정렬이 되어있어야 한다. newA[d] = array[i]로 자릿값에 수를 할당하기 전에, 조건을 검사해서 넣을지, 넘어갈지를 정한다.
def dfs(array, visit, d, newA):
if d == len(array) :
print(' '.join(map(str, newA)))
for i in range(len(array)):
if visit[i] : continue
if i>0 and array[i-1] == array[i] and (visit[i-1]) : continue
newA[d] = array[i]
visit[i] = True
dfs(array, visit, d+1, newA)
visit[i] = False
array = [1,1,2,3]
visit = [False, False, False, False]
newA=[0,0,0,0]
dfs(array, visit, 0, newA)
newA의 d번째 자리에 첫번째 '1'이 들어간 뒤 나오는 조합과, 두번째 '1'이 들어가서 나오는 조합은 같다.
따라서 첫번째 '1'이 이미 사용된 후라면, 두번째 '1'은 newA의 d번째 자리에 넣어주지 않는다.
i>0 and array[i-1] == array[i] and (visit[i-1])
(visit[i-1]) : i-1번째가 이미 사용되었는지 확인
i>0 and array[i-1] == array[i] : 앞의 요소가 나의 요소와 값이 같은지 확인
3. m으로 나누어지는 수만 구하기
이제 m으로 나누어지는 수만 구하도록 고도화 해보자.
m으로 나누어지는지의 여부는 실제 케이스를 줄이지는 않고, 결과값의 답만 도출하는데 사용된다.
m=3이라고 가정하고, 다음 예시를 생각해보자
3000, 또는 3xxx : 앞자리 '3'은 3으로 나누어진다. 나머지는 0이다.
36xx : '36'은 3으로 나누어 진다. 나머지는 0이다.
362x : '362'는 3으로 나누어지지 않는다. 나머지는 2이다.
3621 : '3621'은 3으로 나누어진다.
위의 예시대로 다음과 같은 규칙을 둘 수 있다.
현재까지의 수가 m으로 나누어 진다. -> 나머지 0을 전달한다
현재까지의 수가 m으로 나누어 지지 않는다. -> 나머지 r을 전달한다.
다음 자리수에서 나머지 계산은, (인자로 들어온 r*10 + 현재 자리 값) % m 을 통해 구할 수 있다.
이제 숫자 조합에서 count도 함께 구해보자
m=2
count = 0
def dfs(array, visit, d, newA, r):
global count
if d == len(array) :
if r != 0 : return
print(' '.join(map(str, newA)))
count+=1
return
for i in range(len(array)):
if visit[i] : continue
if i>0 and array[i-1] == array[i] and (visit[i-1]) : continue
newA[d] = array[i]
visit[i] = True
dfs(array, visit, d+1, newA, (r*10+array[i])%m)
visit[i] = False
array = [1,2,5,7]
visit = [False, False, False, False]
newA=[0,0,0,0]
dfs(array, visit, 0, newA, 0)
print(count)
참고로 이렇게 count를 함수 안에서 배치할 수 있다. (분할정복 처럼)
m=2
def dfs(array, visit, d, newA, r):
count=0
if d == len(array) :
if r != 0 : return 0
print(' '.join(map(str, newA)))
return 1
for i in range(len(array)):
if visit[i] : continue
if i>0 and array[i-1] == array[i] and (visit[i-1]) : continue
newA[d] = array[i]
visit[i] = True
count += dfs(array, visit, d+1, newA, (r*10+array[i])%m)
visit[i] = False
return count
array = [1,2,5,7]
visit = [False, False, False, False]
newA=[0,0,0,0]
cnt = dfs(array, visit, 0, newA, 0)
print(cnt)4. 현재 숫자 n 보다 작은 숫자만 구하기(다시)
현재 자릿수를 넣을때, 지금 수가 기존 수(origin)보다 작은 지 구하는 방법은?
이전 자릿수를 넣을때, 한번이라도 작은 수가 들어갔다면 현재에 어떤 값을 넣더라도 기존 수 보다 작을 것이다.
만약 같은 수만 넣은 상태에서, 현재 넣으려는 수가 origin보다 크다면 넣지 않아야 한다.
m=2
def dfs(array, visit, d, newA, r, isSmall):
count=0
if d == len(array) :
if r != 0 : return 0
print(' '.join(map(str, newA)))
return 1
for i in range(len(array)):
if visit[i] : continue
if i>0 and array[i-1] == array[i] and (visit[i-1]) : continue
if not isSmall and (array[i] > origin[d]) :
continue
newA[d] = array[i]
visit[i] = True
if (array[i] < origin[d]) :
count += dfs(array, visit, d + 1, newA, (r * 10 + array[i]) % m, True)
else :
count += dfs(array, visit, d+1, newA, (r*10+array[i])%m, isSmall)
visit[i] = False
return count
origin = [5,2,1,7]
array = [1,2,5,7]
visit = [False, False, False, False]
newA=[0,0,0,0]
cnt = dfs(array, visit, 0, newA, 0, False)
print(cnt)
if (array[i] < origin[d]) : 한번이라도 작은 수가 걸린다면, 다음부터는 무조건 True로 진행한다.
if not isSmall and (array[i] > origin[d]) : : 이전까지 같거나 최초였으나, 현재 수가 origin보다 크기때문에 더이상 진행하지 않는다.
이제 기본 로직은 모두 적용했음으로, 문제를 풀기 위한 전체 코드를 살펴보자
- 최종까지
isSmall이 False라면 origin과 newA가 같은 수라는 뜻으로, return 0을 한다.
import sys
input = sys.stdin.readline
def dfs(array, visit, d, newA, r, isSmall):
count=0
if d == len(array) :
if r != 0 : return 0
if not isSmall : return 0 # 한번도 작은적 없음 == 같은 수
return 1
for i in range(len(array)):
if visit[i] : continue
if i>0 and array[i-1] == array[i] and (visit[i-1]) : continue
if not isSmall and (array[i] > origin[d]) :
continue
newA[d] = array[i]
visit[i] = True
if (array[i] < origin[d]) :
count += dfs(array, visit, d + 1, newA, (r * 10 + array[i]) % m, True)
else :
count += dfs(array, visit, d+1, newA, (r*10+array[i])%m, isSmall)
visit[i] = False
return count % 1000000007
tc = int(input())
for i in range(tc) :
n, m = map(int, input().split())
origin = [int(digit) for digit in str(n)]
array = sorted(origin)
visit = [False for _ in range(len(origin))]
newA=[0 for _ in range(len(origin))]
cnt = dfs(array, visit, 0, newA, 0, False)
print(cnt % 1000000007)
까지 하면 완성인줄 알았는데, 시간초과가 났다.
좀더 찾아보니 visit 배열 대신 비트마스킹으로 풀어야 한다고 한다.
dp의 세계는 정말 끝이 없구나...
아쉽지만 이 문제는 여기서 포기!
다음번에 마음을 가다듬고 다시 풀어봐야겠다.
