글 읽기 - 계속 틀렸습니다가 뜨는데 반례를 찾을 수 있을까요..?

rlwjd31 2년 전 0

재귀를 이용하면 되겠다 했다가…. 시간초과가 나서

DP 메모이지에이션으로 다시 작성했습니다…..

시간이 너무 걸리면 시간초과가 나서 알 수 있겠는데…. 그냥 틀렸습니다만 나오니… ㅜㅜ

손으로 계산해서 해봐도 다 맞아서 질문 올려봅니다… ㅜㅜ

고수님들 도와주세요 ㅜㅜ

반례가 있을까요??

house_dict = {}

def dfs(floor, room_num):
    result = 0

    if floor == 0:
        house_dict[str(floor) + str(room_num)] = room_num + 1
        return house_dict[str(floor) + str(room_num)]
    elif room_num == 0:
        house_dict[str(floor) + str(room_num)] = 1
        return house_dict[str(floor) + str(room_num)]

    try:
        if house_dict[str(floor) + str(room_num)]:
            return house_dict[str(floor) + str(room_num)]
    except:
        for hosu in range(0, room_num + 1):
            result += dfs(floor - 1, hosu)
    house_dict[str(floor) + str(room_num)] = result

    return house_dict[str(floor) + str(room_num)]


loop = int(input())

for _ in range(loop):
    k = int(input())
    n = int(input())
    print(dfs(k, n - 1))

lys7aves 2년 전 0

문자열로 처리하시면 11층 1호와 1층 11호를 구분 못하지 않나요?

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

문제

문제

출처

ICPC

계속 틀렸습니다가 뜨는데 반례를 찾을 수 있을까요..?

rlwjd31 2년 전 0

lys7aves 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말