글 읽기 - 감소하는 수 파이썬 41%에서 틀리는 데 반례 부탁드립니다

kth2642 2년 전 0

i자리의 j로 시작하는 감소수의 개수는 i-1자리의 0부터 j - 1까지의 수로 시작하는 감소수의 개수의 합이라는 걸 아이디어로 해서 백트레킹으로 코드를 짜봤습니다

며칠째 푸는데 답이 안보이네여..

from copy import deepcopy
N = int(input())
cache = [[0 for _ in range(10)] for _ in range(11)]
for i in range(1, 10):
    cache[1][i] = 1
cache[1][0] = 1
for i in range(2, 10):
    for j in range(10):
        for k in range(j):
            cache[i][j] += cache[i - 1][k]
cache[10][9] = 1

sum_cache = deepcopy(cache)

for i in range(1, 11):
    for j in range(10):
        if j == 1:
            sum_cache[i][j] += sum_cache[i - 1][9]
        else:
            sum_cache[i][j] += sum_cache[i][j - 1]

for i in range(11):
    cache[i][0] = 0
cache[1][0] = 1

for i in range(11):
    for j in range(1, 10):
        cache[i][j] += cache[i][j - 1]

def backtracking(N, i, j):
    if i < 1:
        return ""
    if cache[i][j] == N:
        return str(j) + backtracking(N - cache[i][j] + 1, i - 1, 0)
    if cache[i][j - 1] < N < cache[i][j]:
        return str(j) + backtracking(N - cache[i][j - 1], i - 1, 0)
    else:
        return backtracking(N, i, j + 1)

def decrease_number(N, i, j):
    for i in range(1, 11):
        for j in range(10):
            if sum_cache[i][j] == N:
                return str(j) + backtracking(N - sum_cache[i][j] + 1, i - 1, 0)
            if sum_cache[i][j - 1] < N < sum_cache[i][j]:
                return str(j) + backtracking(N - sum_cache[i][j - 1], i - 1, 0)
    return -1

if N == 0:
    print(0)
else:
    print(decrease_number(N, 1, 1))

20wjsdudtj 2년 전 0

120 치면 843 나와야 되는데 840 나오시네여

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

감소하는 수 파이썬 41%에서 틀리는 데 반례 부탁드립니다

kth2642 2년 전 0

20wjsdudtj 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말