[Algorithm🧬] 백준 5921 : Escaping the Farm

문제

시간 초과.

일단 순서까진 생각할 필요가 없음. N 마리 소 중 어떤 조합을 태울 수 있는지만 생각하면 됨.
지금까지 소의 합, 새로운 소 를 더했을 때 자리 올림이 발생하지 않으면 그 소를 태우고,
발생하면 그 소는 안태우고 다음으로 넘어가본다.

import sys
readl = sys.stdin.readline

def upper(n, m):
    sn = list(str(n))[::-1]
    sm = list(str(m))[::-1]

    # max_len = max(len(sn), len(sm))
    min_len = min(len(sn), len(sm))

    # 자리 올림이 발생하면 False
    for i in range(min_len):
        if int(sn[i]) + int(sm[i]) >= 10:
            return False

    # 자리 올림이 발생하지 않으면 True
    return True




def DFS(level, weight, cnt, start):
    global max_cnt
    
    # 지금까지 찾은 그룹 + 앞으로 할 레벨의 수 가
    # 지금까지 찾은 가능한 가장 큰 소 그룹보다 개수가 작다면 굳이 할 필요 없음.
    if cnt + (N - level) <= max_cnt:
        return

    if level == N:
        print(*res, cnt)
        if max_cnt < cnt:
            max_cnt = cnt
        return
    
    for i in range(start, N):
        if ch[i] == 0:
            ch[i] = 1
            if upper(weight, cows[i]):
                res[level] = i
                DFS(level + 1, weight + cows[i], cnt + 1, start + 1)
            else:
                DFS(level + 1, weight, cnt, start + 1)
            ch[i] = 0


N = int(readl())
cows = [int(readl()) for _ in range(N)]

ch = [0] * N
res = [-1] * N
min_weight = N * 100000000
max_cnt = 0
DFS(0, 0, 0, 0)
print(max_cnt)

정답 코드

근데 이상해서 보니까..
1. max_cnt 를 앞에서 갱신을 안해주고 있어서 첫번째 if 문에서 더 많은 경우를 거르지 못했음.
2. 위의 코드가 for 문을 start 부터 시작해서 중복을 조금 피하고 있긴 했으나,
ch 넣어서 start 뒷부분은 순열로 생각하고 있어서 문제였고, 조합이므로 굳이 for 문으로 돌릴 필요도 없었다.

import sys
readl = sys.stdin.readline

def upper(n, m):
    sn = list(str(n))[::-1]
    sm = list(str(m))[::-1]

    # max_len = max(len(sn), len(sm))
    min_len = min(len(sn), len(sm))

    # 자리 올림이 발생하면 False
    for i in range(min_len):
        if int(sn[i]) + int(sm[i]) >= 10:
            return False

    # 자리 올림이 발생하지 않으면 True
    return True



def DFS(level, weight, cnt):
    global max_cnt
    if max_cnt < cnt:
        max_cnt = cnt
    
    # 지금까지 찾은 그룹 + 앞으로 할 레벨의 수 가
    # 지금까지 찾은 가능한 가장 큰 소 그룹보다 개수가 작다면 굳이 할 필요 없음.
    if cnt + (N - level) <= max_cnt:
        return

    if level == N:
        # print(*res, cnt)
        return

    
    # 자리올림이 안 생기면 넣는것도 가고 안넣는 것도 가고,
    if upper(weight, cows[level]):
        res[level] = level
        DFS(level + 1, weight + cows[level], cnt + 1)

    # 자리올림이 생기면 안넣는거만 감.
    DFS(level + 1, weight, cnt)


N = int(readl())
cows = [int(readl()) for _ in range(N)]

ch = [0] * N
res = [-1] * N
max_cnt = 0
DFS(0, 0, 0)
print(max_cnt)