백준 3474번 교수가 된 현우(C++)

문제

정답 코드

#include <iostream>
#include<algorithm>
#include <string>
#include <vector>

using namespace std;
int t_n;
int f_n;

int main()
{
	ios:: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	int a;
	for(int i = 0; i < n; i++){
		cin >> a;
		int ret2 = 0, ret5 = 0;
		for(int j = 2; j <= a; j *= 2){
			ret2 += a / j;
		}
		for(int j = 5; j <= a; j *= 5){
			ret5 += a / j;
		}
		cout << min(ret2, ret5) << "\n";
	}
	return 0;
}

문제 풀이의 흐름

• 이 문제는 그냥 숫자를 늘려가면서 풀면 안된다.

• 2의 배수가 몇개인지, 5의 배수가 몇개인지 세서 둘중에 적은걸 정답으로 생각하면된다.

• 이게 무슨말이냐면 예를들어 5 팩토리얼을 보면 5*4*3*2*1이니까 2의 배수의 갯수는 4에서 2개 2에서 1개 해서 총 3개이고 5의 배수는 5 한개 해서 둘중 작은 값은 5 한개로 1이다.

• 위의 답은 총 10의 배수의 갯수를 알려줄 수 있다.

• 우리는 이것만 생각하면 밑의 오답코드가 나온다.

• 한가지 성질을 더 활용해야 하는데

• 예를들어 10 팩토리얼을 볼 때 2의 배수의 갯수는 2,4,6,8,10이고 4의 배수는 4,8 이다. 8의 배수는 8이다.

• 이 성질을 활용하면 10을 2로 나눴을 때 갯수(5개) + 10을 4로 나눴을 때 갯수(2개)+ 8로나눴을때 (1개) 이렇게 나오니까 이 것들을 다 더하면 우리는 2가 몇개인지 알 수가 있다.

• 5 역시 위와 같다. 100팩토리얼의 경우 5로 나누면 20개 (5,10,15,20…100)이렇게 되고 25로 나누면 (25,50,75,100)이렇게 4개가 된다. 따라서 5도 총 5의 배수가 몇개인지알 수가있다.

• 이를 일반화 하면 2와 5를 제곱해가며 나눈 값들을 더하면 되는 것이다.

• 코드 구현은 위와 같다.

주의 할 점

이 문제는 한번 실패하면 빠르게 다른 로직으로 넘어가야 한다. 시간적으로 시간 초과가 났다는 건 더 간단한 방법이 있다는 것인데 자꾸만 간단한 방법만 찾으려 해서 오히려 더 오래 걸린 것 같다.

급하게 풀 생각하지말고 조금 더 천천히 풀어보도록 하자!!

반성 및 고찰

내가 피곤해서 그런건지 아니면 그냥 문제를 잘 못푸는건지 알고리즘을 풀 때 정말 어려웠던게 티어가 낮을 때면 살짝 슬퍼진다..ㅠㅠㅠㅠ

오답코드

#include <iostream>
#include<algorithm>
#include <string>
#include <vector>

using namespace std;
int t_n;
int f_n;

int main()
{
	ios:: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for (int i=0;i<n;i++)
	{
		long long num;
		cin >> num;
		int tnum = num;
		while (num)
		{
			if (tnum%4 == 0)
			{
				t_n+=2;
				tnum = tnum/4;
			}
			else if (tnum%2 == 0)
			{
				t_n++;
				tnum = tnum/2;
			}
			else if (tnum%25 == 0)
			{
				f_n+=2;
				tnum=tnum/25;
			}
			else if (tnum%5 == 0)
			{
				f_n++;
				tnum=tnum/5;
			}
			else
			{
				num--;
				tnum = num;
			}
		}
		cout << min(t_n,f_n) << "\n";
		t_n=0;
		f_n=0;
	}
}

처음에 2 5 의 갯수를 나눠지는 만큼 세서 그 값을 했는데.. 이거는 엄청 오래걸리더라.. 다른 방법을 시도해봐야겠다.

두번째 실패 이건 뻘짓

#include <iostream>
#include<algorithm>
#include <string>
#include <vector>

using namespace std;
int t_n;
int f_n;
int result[1000000001];

int main()
{
	ios:: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector <int>arr;

	vector <int>backup;
	for (int i=0;i<n;i++)
	{
		int num;
		cin >> num;
		arr.push_back(num);
		backup.push_back(num);
	}
	sort(arr.begin(),arr.end());
	int num = arr[0];
	int tnum = num;
	while (num)
	{
			if (tnum%4 == 0)
			{
				t_n+=2;
				tnum = tnum/4;
			}
			else if (tnum%2 == 0)
			{
				t_n++;
				tnum = tnum/2;
			}
			else if (tnum%25 == 0)
			{
				f_n+=2;
				tnum=tnum/25;
			}
			else if (tnum%5 == 0)
			{
				f_n++;
				tnum=tnum/5;
			}
			else
			{
				result[num]=min(t_n,f_n);
				num--;
				tnum = num;
			}
		}
	for (int i=0;i < n;i++)
	{
		cout << result[backup[i]] << "\n";
	}
}

이건 아에 쓰레기 코드이다.

이미 이전에 가장 큰 값을 구할 때 가장 작은 팩토리얼 값 역시 당연하게 구해진다고 생각했는데, 그건 또 말이 안됐다. 가장 작은 값부터 정답을 채워나가는게 더 맞는 것 같다.

다시 생각해보자.

#include <iostream>
#include<algorithm>
#include <string>
#include <vector>

using namespace std;
int t_n;
int f_n;

int main()
{
	ios:: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector <int>arr;
	vector <int>backup;
	for (int i=0;i<n;i++)
	{
		int num;
		cin >> num;
		arr.push_back(num);
		backup.push_back(num);
	}
	vector <int>result;
	sort(arr.begin(),arr.end());
	int bef_num = 0;
	for (int i=0;i<n;i++)
	{
		int num = arr[i];
		// long long num;
		// cin >> num;
		int tnum = num;
		while (num > bef_num)
		{
			if (tnum%4 == 0)
			{
				t_n+=2;
				tnum = tnum/4;
			}
			else if (tnum%2 == 0)
			{
				t_n++;
				tnum = tnum/2;
			}
			else if (tnum%25 == 0)
			{
				f_n+=2;
				tnum=tnum/25;
			}
			else if (tnum%5 == 0)
			{
				f_n++;
				tnum=tnum/5;
			}
			else
			{
				num--;
				tnum = num;
			}
		}
		result.push_back( min(t_n,f_n));
		bef_num = arr[i];
		// t_n=0;
		// f_n=0;
	}
	for (int i=0;i < n;i++)
	{
		for (int j=0;j < n;j++)
		{
			if (backup[i] == arr[j])
				cout << result[j] << "\n";
		}
	}
	// cout << min(t_n,f_n) << "\n";
}

이번에는 진짜 맞았다고 생각했는데 뭐가 문제일까…?

이렇게 생각했었다. 앞으론 손으로 적고 코드짜기!!

Uploaded by N2T