글 읽기 - 답은 맞았는데 이것도 동적 프로그래밍으로 봐도 옳은 걸까요??

jyc4836 3년 전 2

별도의 배열을 생성하고, n == 3일 때까지의 값만 미리 준 다음 함수 호출 시 기존에 cache 안에 있던 값이면 그대로 반환하고 아닐 경우면 값을 계속 계산해서 미리 cache에 저장해 올려 나가는 식인데 이것도 memoization을 사용한 거라고 봐도 좋은지 모르겠네요!

n = int(input())

cache = [-1] * 12
cache[0] = 0 
cache[1] = 1 
cache[2] = 2 
cache[3] = 4

def fn(a):
    if cache[a] != -1:
        return cache[a]
    for i in range(4, a + 1):
        cache[i] = cache[i - 1] + cache[i - 2] + cache[i - 3]
    return cache[a]

for _ in range(n):
    print(fn(int(input())))

dohoon 3년 전 4

동적 프로그래밍이 아닐 이유는 없습니다.

다만, 작성자님이 궁금하신 점은 배열 하나에 방문 여부와 고유값을 동시에 넣는 것이 옳은 행동인가를 물어보시는 것으로 알아들었습니다.

간단한 문제에서는 작성자님처럼 트릭을 이용해도 좋습니다.

하지만 DP는 앞으로 상당히 많이 변형될 것이므로 memo를 쓰지 않으려도 쓸 수 밖에 없는 상황이 올 겁니다.

참고로 저도 간단한 DP 문제들은 작성자님과 같은 방식으로 풉니다.

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

문제

문제

출처

ICPC

답은 맞았는데 이것도 동적 프로그래밍으로 봐도 옳은 걸까요??

jyc4836 3년 전 2

dohoon 3년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말