글 읽기 - 반례가 있는걸까요..

imoneleft 5년 전 0

틀렸습니다. 가 뜹니다.

많이들 틀리는 30, 50, 100등을 입력해봐도 제대로 잘 나옵니다.

왜 틀린걸까요?

#include <iostream>
using namespace std;

int main()
{
	int num, result = 0;
	cin >> num;

	while (true)
	{
		if (num == 1)
			break;
		else if (num % 3 == 0)
		{
			result++;
			num /= 3;
			if (num == 1)
				break;
		}
		else if ((num - 1) % 3 == 0)
		{
			num--;
			result++;
			if (num == 1)
				break;
		}
		else if(num % 3 != 0 && (num - 1) % 3 != 0)
		{
			if (num % 2 == 0)
			{
				result++;
				num /= 2;
			}
			else
			{
				num--;
				result++;
			}
			if (num == 1)
				break;
		}
	}


	cout << result;
	return 0;
}

jaehoo1 5년 전 0

100000

넣으면 18 나와야 합니다

imoneleft 5년 전 0

100000
99999 1
33333 2
11111 3
11110 4
11109 5 5555
3703 6 5554
3702 7 2777
1234 8 2776
1233 9 1388 2775
411 10
137 11
136 12
135 13 68
45 14 34
15 15 33
5 16
4 17
2 18
1 19

아무리 해도 19번까지밖에 안나옵니다. 어떻게 18번이 나오는 건가요?

아직 규칙을 못찾았네요..

djm03178 5년 전 2

규칙을 찾는 문제가 아니라, 최적의 방법을 프로그램에게 찾아내게 하는 문제입니다. n/3, n/2, n-1 중 최적인 것을 프로그램이 고르면 되는 문제입니다.

imoneleft 5년 전 0

감사합니다 해결하였습니다!

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

문제

문제

출처

ICPC

반례가 있는걸까요..

imoneleft 5년 전 0

jaehoo1 5년 전 0

imoneleft 5년 전 0

djm03178 5년 전 2

imoneleft 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말