글 읽기 - 어떤 부분에서 틀린지 너무 궁금합니다..

kkw564 7년 전 0

지수적 DP를 생성하여 MAP을 이용하여 제작하였는데 어느 부분에서 틀린지 잘 모르겠네요 ㅠㅠ

cout부분 주석을 제거하면 어떻게 작동하는지 알 수 있습니다 ㅠㅠ!

#include <iostream>
#include <cstdio>
#include <map>
#include <math.h>

using namespace std;

map<long long int, long long int> m;

long long int p, q;
long long int ans;
long long int pq;
long long int _max;

void dfs(long long int n)
{
	if(n / p > _max)
		dfs(n / p);

		auto it = m.lower_bound(n / p);
	//	cout << "내가본1 it :: " << it->first << endl;
		ans += it->second - 1;

	//	ans += m[n / q];
	if(n / q > _max)
		dfs(n / q);

		it = m.lower_bound(n / q);
	//	cout << "내가본2 it :: " << it->first << endl;
		ans += it->second - 1;
}
int main()
{
	long long int n;
	scanf("%lld %lld %lld", &n, &p, &q);
	m[0] = 1;

	int tmp;
	if (p > q)
	{
		tmp = p;
		p = q;
		q = tmp;
	}

	int val = 1;
	for (long long int i = 1, j = 1; i <= n; i *= p, j *= q)
	{
		m[i] = val++;
	//	cout << "1 i :: " << i << " m[i] :: " << m[i] << endl;
		m[j] = val++;
	//	cout << "2 i :: " << j << " m[j] :: " << m[i] << endl;
	}

	for (long long int i = 1; i <= n; i *= q)
	{
	}
	
	for (auto it = m.begin(); it != m.end(); it++)
	{
	//	cout << it->first << " " << it->second << endl;
		if (it->first > _max)
			_max = it->first;
	}

	//cout << "_max :: " << _max << endl;
	dfs(n);


	printf("%lld", ans);

	return 0;
}

cprayer 7년 전 0

해당 부분을 왜 저렇게 작성했는지 모르겠습니다

반례입니다.

20 2 2

for (long long int i = 1, j = 1; i <= n; i *= p, j *= q)
{
m[i] = val++;
// cout << "1 i :: " << i << " m[i] :: " << m[i] << endl;
m[j] = val++;
// cout << "2 i :: " << j << " m[j] :: " << m[i] << endl;
}

kkw564 7년 전 0

제가 생각했을 때는 DP값의 고정이 다음과 같이 된다고 생각했습니다.

예를들어 1000000 500 600일 경우

DP[0] :: 1

DP[1~499] :: 2

DP[500~599] :: 3

DP[600~249999] :: 4

DP[250000~359999] :: 5

DP[360000~끝] :: 6

이라고 생각하여 풀어서 다음과같이 코드를 작성하였는데

이렇게 생각한 DP값이 틀린건가요??

kkw564 7년 전 0

반례를 통해 제 코드가 틀렸음은 이해가 되지만 그 뒤로 어떻게 손을 봐야할지 잘 감이안오네요ㅠ

cprayer 7년 전 1

정의를 그대로 이용하시는게 낫습니다. 즉 함수의 인자로 i가 들어왔을 때

m[i]가 매핑되어 있지 않다면 m[i / p], m[i / q]를 인자로 재귀호출하고 리턴된 값을 토대로 매핑하시면 됩니다.

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

문제

문제

출처

ICPC

어떤 부분에서 틀린지 너무 궁금합니다..

kkw564 7년 전 0

cprayer 7년 전 0

kkw564 7년 전 0

kkw564 7년 전 0

cprayer 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말