글 읽기 - 어느부분이 잘못되었는지 도움좀 구해봅니다.

smu04129 2년 전 0

고수분들의 도움을 구해봅니다..

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int n, dp[1000001];

int solve(int num, int cnt) {
	if (num == 1) { return cnt; }
	int& ret = dp[num];
	if (ret != -1) { return ret; }
	ret = numeric_limits<int>::max();
	if (num % 3 == 0) { ret = min(ret, solve(num / 3, cnt + 1)); }
	if (num % 2 == 0) { ret = min(ret, solve(num / 2, cnt + 1)); }
	ret = min(ret, solve(num - 1, cnt + 1));
	return ret;
}

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

dldyddlwl 2년 전 1

10이라는 예시를 생각해봅시다! 더 많은 경우가 있지만 이렇게 2가지 경우를 봅시다.

10 -> 5 -> 4 -> 3 -> 1, cnt로 dp값이 정해지므로, dp[3]의 값이 이 경로로 정해져 버립니다. ( dp[3] = 4 )

10 -> 9 -> 3 -> 1, 그렇게 되면 이 과정에서 dp[3]은 이전 경로의 값을 가지고 있게 되면서, 현재 경로가 제대로 처리되지 못하게 됩니다.

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

문제

문제

출처

ICPC

어느부분이 잘못되었는지 도움좀 구해봅니다.

smu04129 2년 전 0

dldyddlwl 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말