글 읽기 - dp로 풀면 왜 메모리 초과가 뜰까요?

aj4941 3년 전 1

이 문제를 일단 bfs로 해결하긴 했습니다.

근데 dp로도 풀 수 있을 것 같아서 탑다운 방식으로 코드를 작성해봤는데 메모리초과가 나더군요.

범위는 0 ~ k * 2로 지정해서 메모리초과가 날 수 없는 것 같은데 왜 메모리초과가 나는지 궁금합니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
ll n, k;
ll dp[250000];

ll solve(ll n)
{
    if(n < 0 || n > k * 2) return INT_MAX / 2;
    if(n == k) return 0;
    ll &ret = dp[n];
    if(ret != -1) return ret;
    ll cnt = min(solve(n - 1) + 1, solve(n + 1) + 1);
    return ret = min(cnt, solve(n * 2) + 1);
}

int main(void)
{
    ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	memset(dp, -1, sizeof dp);
	cin >> n >> k;
	cout << solve(n);
}

ghkdiwl 3년 전 0

문제에 n이 k보다 작다는 조건이 없어서

n이 17 k가 5 로 입력이 주어질수도 있지 않나요? ㅇ..ㅇ

그럼 solve들어가서 아무것도 못하고 나올거같아용

aj4941 3년 전 0

2 * k부분을 300000 으로 설정해봤는데 그래도 안되네요 ㅠ

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

문제

문제

출처

ICPC

dp로 풀면 왜 메모리 초과가 뜰까요?

aj4941 3년 전 1

ghkdiwl 3년 전 0

aj4941 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말