문제
정답 코드
#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