Problem p03128 (python)

Fixed submission:
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)


N, M = list(map(int, input().split()))
A = list(map(int, input().split()))

num_dict = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}
A.sort(reverse=True)

# dpを計算
dp = defaultdict(lambda: -1e18)
dp[0] = 0

for i in range(2, N+1):
    dp[i] = max([dp[i-num_dict[a]]+1 for a in A])

num_count = dp[N]

out_list = []
res_N = N
for _ in range(num_count):
    for a in A:
        if dp[res_N]-1 == dp[res_N-num_dict[a]]:
            out_list.append(str(a))
            res_N = res_N - num_dict[a]
            break

print(''.join(out_list))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)


N, M = list(map(int, input().split()))
A = list(map(int, input().split()))

num_dict = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}

# Aの各要素の画数
count_list = [num_dict[a] for a in A]

# 最小の画数
min_matches = min(count_list)

# 画数の最小の値のうち最大の数値
min_num_list = []
[min_num_list.append(a) for a in A if num_dict[a] == min_matches]
min_num = max(min_num_list)


# 数値とあまり消化数のペア
A.sort(reverse=True)
res = {a: num_dict[a]-min_matches for a in A}


def dfs(nums, target, num_count):
    if len(nums) > num_count:
        return None

    if target > 0:
        for a in A:
            ret = dfs(nums+[a], target-res[a], num_count)
            if ret is not None:
                return ret
        return None
    elif target == 0:
        return nums
    else:
        return None


# dpを計算
dp = defaultdict(lambda: -1e18)
dp[0] = 0
dp[1] = 0

for i in range(2, N+1):
    dp[i] = max([dp[i-num_dict[a]]+1 for a in A])


num_count = dp[N]
# あまりの本数
mod = N - min_matches*num_count

# あまりをどう分配するか(DFS)
share = dfs([], mod, num_count)
out_list = sorted([min_num]*(num_count-len(share))+share, reverse=True)
out_list = [str(item) for item in out_list]
print(''.join(out_list))

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))

num_dict = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}

# Aの各要素の画数
count_list = [num_dict[a] for a in A]

# 最小の画数
min_matches = min(count_list)

# 画数の最小の値のうち最大の数値
min_num_list = []
[min_num_list.append(a) for a in A if num_dict[a] == min_matches]
min_num = max(min_num_list)


# 数値とあまり消化数のペア
A.sort(reverse=True)
res = {a: num_dict[a]-min_matches for a in A}


def dfs(nums, target, num_count):
    if len(nums) > num_count:
        return None
    if target == 0:
        return nums
    elif target < 0:
        return None
    else:
        for a in A:
            ret = dfs(nums+[a], target-res[a], num_count)
            if ret is not None:
                return ret
        return None


for num_count in range(N//min_matches, 0, -1):
    # あまりの本数
    mod = N - min_matches*num_count

    # あまりをどう分配するか(DFS)
    share = dfs([], mod, num_count)
    if share is not None:
        out_list = sorted([min_num]*(num_count-len(share))+share, reverse=True)
        out_list = [str(item) for item in out_list]
        print(''.join(out_list))
        break

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))

num_dict = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}

# Aの各要素の画数
count_list = [num_dict[a] for a in A]

# 最小の画数
min_matches = min(count_list)

# 画数の最小の値のうち最大の数値
min_num_list = []
[min_num_list.append(a) for a in A if num_dict[a] == min_matches]
min_num = max(min_num_list)


# 数値とあまり消化数のペア
A.sort(reverse=True)
res = {a: num_dict[a]-min_matches for a in A}


def dfs(nums, target, num_count):
    if len(nums) > num_count:
        return None
    if target == 0:
        return nums
    elif target < 0:
        return None
    else:
        for a in A:
            ret = dfs(nums+[a], target-res[a], num_count)
            if ret is not None:
                return ret
        return None


for num_count in range(N//min_matches, 0, -1):
    # あまりの本数
    mod = N - min_matches*num_count

    print(num_count, mod, num_count)

    # あまりをどう分配するか(DFS)
    share = dfs([], mod, num_count)
    if share is not None:
        out_list = sorted([min_num]*(num_count-len(share))+share, reverse=True)
        out_list = [str(item) for item in out_list]
        print(''.join(out_list))
        break