글 읽기 - 1로가는 수 2 반례나 틀린부분 지적 부탁드립니다ㅜㅜ

gpfqpsxj75 3년 전 0

안녕하세요 몇시간째 고민하다가 다른분 코드를 참고해서 했는데도 안되서 질문드립니다.

처음엔 바텀업 방식으로 풀었는데, n이 10000이 넘어가면 재귀호출 깊이가 깊어져서인지 비주얼에서도 제대로 안되고, 제출해도 바로 틀렸습니다가 나왔습니다.

그래서 두번째는 탑다운 + 바텀업을 짬뽕으로 섞어놓은 방식을 사용하여 풀었습니다. 그런데 39%쯤에서 또 틀렸습니다가 나왔습니다.

1로가는 수를 출력하는 부분이 틀렸는지, 아니면 최소횟수를 구하는 방법이 틀렸는지 도저히 감이 안잡힙니다.

도움주시는 평생 행복하길 기원하겠습니다.

#include <iostream>

using namespace std;

int DP[1000001], result = 2000000000;

int getResult(int n, int count);
int min(int a, int b) {
	return a < b ? a : b;
}

int main() {
	int temp;
	cin >> temp;
	getResult(temp, 0);
	cout << result << "\n";

	//1로 가는 수 출력
	int minResult = DP[temp];
	int cur = temp;
	while (cur >= 1) {
		cout << cur << " ";
		if (cur == 1)
			break;
		minResult--;
		if (DP[cur - 1] == minResult) {
			cur -= 1;
		}
		else if (cur % 2 == 0 && DP[cur / 2] == minResult) {
			cur /= 2;
		}
		else if (cur % 3 == 0 && DP[cur / 3] == minResult) {
			cur /= 3;
		}
	}
}
//바텀업 방식으로 푼 코드
int getResult(int n) {
	if (DP[n] != 0) {
		return DP[n];
	}
	if (n == 1) 
		return 0;

	int answer = 2000000000;
	if (n % 3 == 0)
		answer = min(answer, getResult(n / 3) + 1);
	if (n % 2 == 0) 
		answer = min(answer, getResult(n / 2) + 1);
	answer = min(answer, getResult(n -1) + 1);

	return DP[n] = answer;
}

//다른 방식으로 푼 코드
int getResult(int n, int count) {
	if (DP[n] != 0) {
		if (count + DP[n] < result)
			result = count + DP[n];
		return DP[n] + count;
	}
	if (n == 1) {
		if (count < result)
			result = count;
		return count;
	}
	if (count > result)
		return 2000000000;

	int answer = 2000000000;
	if (n % 3 == 0)
		answer = min(answer, getResult(n / 3, count + 1));
	if (n % 2 == 0)
		answer = min(answer, getResult(n / 2, count + 1));
	answer = min(answer, getResult(n - 1, count + 1));
	DP[n] = answer - count;    

	return answer;
}

djm03178 3년 전 1

바텀업 방식은 조금만 고치면 기본적으로 맞는 코드인데, 다른 방식으로 푸신 코드와 섞여서 어느 부분을 실수하셨던 건지는 모르겠습니다.

이 코드에서,

1. 다른 방식으로 푼 코드를 지우고,

2. getResult 함수의 프로토타입을 바텀업 방식의 함수 형태랑 같게 하고,

3. result 대신에 DP[temp]를 출력하게 하면 맞습니다.

gpfqpsxj75 3년 전 0

정말이군요 ㅜㅜ

분명이 바텀업으로 푼거로 제대로 올렸었던거 같은데 어떤 부분에서 실수가 있었던 모양입니다

답변 정말감사합니다!! 평생행복하세요!

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

문제

문제

출처

ICPC

1로가는 수 2 반례나 틀린부분 지적 부탁드립니다ㅜㅜ

gpfqpsxj75 3년 전 0

djm03178 3년 전 1

gpfqpsxj75 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말