글 읽기 - 수정된 코드가 왜 답을 야기하는지 모르겠습니다.

blossomwhale 2년 전 0

점선 위는 수정 전 코드이고, 제출 시 index_err가 발생합니다. 예제 문제는 모두 통과되고, 50 50 50 , -50 -50 -50 그리고 0 근처의 값들에 대해선 대부분 test 해보았습니다.

점선 밑은 수정 후 코드이고, index_err를 위해서 아닌, 효율성을 위해 마지막 출력부분의 else쪽에서 memoization을 매 test_case마다 새로 기록하는것이 아닌, 각 test_case마다 기록하고, 해당 기록을 쭉 사용하는 방식으로 바꿨습니다.

효율성을 위해서 코드를 바꾸고 제출을 했는데, 신기하게 index_err가 사라졌고 이유를 고민해도 어떤 이유에서 index_err가 사라진것인지 이해가 되지않아 질문드립니다.

import sys


def w(a, b, c, _memoization):
    if a <= 0 or b <= 0 or c <= 0:
        return _memoization[0][0][0]

    if a > 20 or b > 20 or c > 20:
        if _memoization[20][20][20] is not None:
            return _memoization[20][20][20]
        else:
            result = w(20, 20, 20, _memoization)
            _memoization[20][20][20] = result
            return result

    if a < b and b < c:
        if _memoization[a][b][c] is not None:
            return _memoization[a][b][c]
        else:
            result = w(a, b, c - 1, _memoization) + w(a, b - 1, c - 1, _memoization) - w(a, b - 1, c, _memoization)
            _memoization[a][b][c] = result
            return result

    if _memoization[a][b][c] is not None:
        return _memoization[a][b][c]
    else:
        result = w(a - 1, b, c, _memoization) + w(a - 1, b - 1, c, _memoization) + w(a - 1, b, c - 1, _memoization) - w(
            a - 1, b - 1, c - 1, _memoization)
        _memoization[a][b][c] = result
        return result


while True:
    a, b, c = sys.stdin.readline().rstrip().split()
    a = int(a)
    b = int(b)
    c = int(c)

    if a == -1 and b == -1 and c == -1:
        break

    if a <= 0 or b <= 0 or c <= 0:
        result = 1
        output = f'w({a}, {b}, {c}) = ' + str(result)
    else:
        memoization = [[[None for _ in range(c + 1)] for _ in range(b + 1)] for _ in range(a + 1)]
        memoization[0][0][0] = 1
        result = w(a, b, c, memoization)
        output = f'w({a}, {b}, {c}) = ' + str(result)

    print(output)

#==========================================================================================

import sys


def w(a, b, c, _memoization):
    if a <= 0 or b <= 0 or c <= 0:
        return _memoization[0][0][0]

    if a > 20 or b > 20 or c > 20:
        if _memoization[20][20][20] is not None:
            return _memoization[20][20][20]
        else:
            result = w(20, 20, 20, _memoization)
            _memoization[20][20][20] = result
            return result

    if a < b and b < c:
        if _memoization[a][b][c] is not None:
            return _memoization[a][b][c]
        else:
            result = w(a, b, c - 1, _memoization) + w(a, b - 1, c - 1, _memoization) - w(a, b - 1, c, _memoization)
            _memoization[a][b][c] = result
            return result

    if _memoization[a][b][c] is not None:
        return _memoization[a][b][c]
    else:
        result = w(a - 1, b, c, _memoization) + w(a - 1, b - 1, c, _memoization) + w(a - 1, b, c - 1, _memoization) - w(
            a - 1, b - 1, c - 1, _memoization)
        _memoization[a][b][c] = result
        return result


memoization = [[[None for _ in range(50 + 1)] for _ in range(50 + 1)] for _ in range(50 + 1)]
memoization[0][0][0] = 1
while True:
    a, b, c = sys.stdin.readline().rstrip().split()
    a = int(a)
    b = int(b)
    c = int(c)

    if a == -1 and b == -1 and c == -1:
        break

    if a <= 0 or b <= 0 or c <= 0:
        result = 1
        output = f'w({a}, {b}, {c}) = ' + str(result)
    else:
        result = w(a, b, c, memoization)
        output = f'w({a}, {b}, {c}) = ' + str(result)

    print(output)

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

문제

문제

출처

ICPC

수정된 코드가 왜 답을 야기하는지 모르겠습니다.

blossomwhale 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말