글 읽기 - DP를 사용하지 않은것 같은데 정답으로 나오네요

rlawhdals94 4년 전 0

이전에 풀었던 BFS 문제랑 비슷해보여서

그 때 사용했었던 함수 그대로 가져와 숫자만 바꿔서 넣었더니

정답으로 나오네요..

DP로는 어떻게 풀어야될까요..

"""
DP - 1로 만들기
"""
import sys


def findNum(n, m):
    queue = dict()
    visited = {n}
    d = 0
    queue[d] = {n}

    while 1:
        ans = queue[d]
        d += 1
        queue[d] = set()
        for num in ans:
            if num == m:
                return d-1

            next_nums = list()
            if num % 3 == 0:
                next_nums.append(num//3)
            if num % 2 == 0:
                next_nums.append(num//2)
            next_nums.append(num-1)

            for next_num in next_nums:
                if next_num not in visited:
                    visited.add(next_num)
                    queue[d].add(next_num)


N = int(sys.stdin.readline().rstrip())
print(findNum(N, 1))

djm03178 4년 전 0

다른 사람들의 코드를 읽어보세요.

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

문제

문제

출처

ICPC

DP를 사용하지 않은것 같은데 정답으로 나오네요

rlawhdals94 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말