글 읽기 - 어디가 잘못된건지 모르겠습니다..

alclstit 7년 전 0

dp가 문제입니다..ㅠㅠ

n이 100만일 때까지 몇몇 테스트케이스를 돌려봤는데 맞게 출력되는것 같습니다만...

어느 테스트케이스가 틀린건지 계속 틀렸다고 뜹니다.

도와주세요!!

풀이는 재귀로 메모이제이션적용해서 풀었고 케이스는 n이 3과 2 로 나눠떨어질때랑 그 이외의 경우 그리고 n-1이 2와3으로 떨어질 경우로 나누어서 최솟값을 찾는 방식으로 구현하였습니다.

#include<iostream>
#include<algorithm>
#define MAX_N 9999999	
using namespace std;
int test1463(int n);
int cache[1000001];
int count = 0;
int main()
{
	int input;
	cin >> input;

	for (int i = 0; i < 1000001; ++i)
	{
		cache[i] = MAX_N;
	}

	if (input == 1)
		cout << 1 << endl;
	else
		cout << test1463(input) << endl;

	return 0;
}



int test1463(int n) 
{
	if (n <= 1) return 0;
	
	int& ret = cache[n];
	if (ret != MAX_N)
		return ret;

	if (n % 2 == 0)
		ret = min(test1463(n / 2) + 1, ret);
	if (n % 3 == 0)
		ret = min(test1463(n / 3) + 1, ret);
	if (n % 2 != 0 && n % 3 != 0)
		ret = min(test1463(n - 1) + 1, ret);
	if ((n - 1) % 2 == 0)
		ret = min(test1463(n / 2) + 2, ret);
	if ((n - 1) % 3 == 0)
		ret = min(test1463(n / 3) + 2, ret);

	return ret;
}

superahn 7년 전 0

-1 연산을 2번 해야 더 빠르게 1이 되는 경우도 있는데, 작성자님 코드에서는 그런 상황에서 동작하지 않는 경우가 있네요.

164를 예로 들면, 이 숫자에서 -2를 하고나서 /2 하면 81이고, 이 숫자는 3의 제곱이니 계속 /3하면 제일 빠릅니다.

그러나 님 코드에서는 164에서 -1을 할 수가 없어요..

superahn 7년 전 0

-1 연산을 특정 조건에서만 할 수 있도록 하셔서 일부 케이스가 누락되는 상황입니다.

alclstit 7년 전 0

//superahn

164의 경우를 해봤는데 164 - 82 - 81 - 27 - 9 - 3 - 1 이런식으로 진행되는것 같지는 않지만 일단 답은 6으로 맞는것같습니다.

이런 비슷한 상황의 다른 테스트케이스에서 틀렸는지도 모르겠군요. 일단 다시 수정해야겠습니다. 답변 감사합니다.

helper 7년 전 0

input으로 1이 입력됬을때는 이미 답인경우이기때문에 0이 출력되야됩니다.

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

문제

문제

출처

ICPC

어디가 잘못된건지 모르겠습니다..

alclstit 7년 전 0

superahn 7년 전 0

superahn 7년 전 0

alclstit 7년 전 0

helper 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말