2024 - 07 - 30 C++ 코딩테스트 10주완성 D+23
백준 3474 문제 - 교수가 된 현우
자연수 N이 주어지면 N!의 오른쪽 끝에 있는 0의 개수를 알려주는 문제
입력
첫째 줄에 테스트 케이스의 개수 T가 주어지고, 이어서 T개의 줄에 정수 N이 주어진다(1 <= N <= 1000000000).
출력
각 줄마다 N!의 오른쪽 끝에 있는 0의 개수를 출력한다.
실습코드
#include <bits/stdc++.h>
using namespace std;
//1.변수 목록
//테스트 케이스 개수를 입력받을 정수형 변수 t;
//입력받을 정수 long long 형 변수 n;
int t, n;
vector<int> tcnt;
vector<int> fcnt;
//2-2-3 int factorial 함수
//2-2-3-1 i = n 부터 n -- 한다음 n > 0 까지
//2-2-3-1-1 무한루프로 반복문을 돌려
//2-2-3-1-2 정수형 지역변수 a 를 선언한다음
//2-2-3-1-3 a = n
//2-2-3-1-4 a % 2 == 0 일때 조건에 들어가면 a = a/2 를 해주고 tcnt++
//2-2-3-1-5 a % 5 == 0 일때 조건에 들어가면 a = a/5 를 해주고 fcnt++
//2-2-3-1-6 else 일시 break;
void factorial(int &n, int& index)
{
for (int i = n; i > 0; i--)
{
int a = i;
while (true)
{
if (a % 2 == 0)
{
a /= 2;
tcnt[index]++;
}
else if (a % 5 == 0)
{
a /= 5;
fcnt[index]++;
}
else break;
}
}
}
int main()
{
//2.알고리즘
//2-1 테스트 케이스의 개수를 입력받는다
//2-2 테스트 케이스 개수만큼 반복문
cin >> t;
for (int i = 0; i < t; i++)
{
fcnt.push_back(0);
tcnt.push_back(0);
//2-2-1 정수 n을 입력받는다.
//2-2-2 입력받은 정수 n을 factorial(n) 안에 매개변수로 넣고 호출한다.
cin >> n;
factorial(n,i);
}
//2-2-3-2 만약 tcnt > fcnt cout << fcnt
//2-3-3-3 else cout << tcnt
//2-3-3-4 tcnt = 0 fcnt = 0;
for (int j = 0; j < fcnt.size(); j++)
{
if (tcnt[j] > fcnt[j])
cout << fcnt[j] << endl;
else
cout << tcnt[j] << endl;
}
}
N!의 0의 개수는 N! 을 소인수 분해 하였을 때,
10의 거듭제곱의 차수를 구하면 알 수 있기때문에
ex) 2534000 는 2534 * 10^3 과 같다. 우리는 0의 개수를 구하려는 것이기때문에 10의 차수만 구하면 된다.
입력받은 N ~ 1 까지의 2 와 5 의 차수를 카운트한다음에 2 x 5 가 10이므로 둘중 하나라도 높은 수가 나오면 높은 차수를 버리고 낮은 차수를 선택해야 (2 x 5)^n 을 구할 수 있다.
이렇게하여 차수를 구하였지만,
코드 시간복잡도가 문제였다.
첫번째 반복문은 N부터 1까지의 실행시켜야 하고,
그 안에서 반복문 임시변수 i 를 2 또는 5로 나누어 떨어지지 않을 때 까지 반복하므로
시간복잡도는 O(N * a) 가 된다.
하지만 N의 입력조건은 1 <= N <= 1,000,000,000 이므로
N = 1,000,000,000 일경우 O(10^9 * a) 의 시간복잡도를 가지게 된다.
시간복잡도가 무지막지하게 크므로 줄일 필요가 있다.
이를 해결할 방법은
입력받은 N을 2의 거듭제곱과 5의 거듭제곱을 N까지 나누어서 나눈 값을 각각 보관하여 작은 차수를 출력시켜주는 것이다.
코드로 쓰면 이렇다.
for (int i = 2; i <= n; i *= 2)
{
ret2 += n / i;
}
for (int i = 5; i <= n; i *= 5)
{
ret5 += n / i;
}
코드로만 보면 잘 이해가 되지 않는다.
나도.. 이해가 잘 되지 않아 10!을 예시로 대충 표로 그려보았다.
정말 2의 거듭제곱으로 나누었을 때 몫이랑.. 2의 거듭제곱의 개수랑 같다..!! 놀랍다
백준 2852 문제 - NBA 농구
농구 경기는 정확히 48분동안 진행된다. 각 팀이 몇 분동안 이기고 있었는지 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 골이 들어간 횟수(1<=N<=100)이 주어진다.
둘째 줄부터 N개의 줄에 득점 정보가 주어진다.
득점 정보는 득점한 팀의 번호와 득점한 시간으로 이루어져 있다.
팀의 번호는 1 또는 2이다. 득점한 시간은 MM:SS(분:초) 형식이며, 분과 초가 한자리일 경우 첫째자리가 0이다.
0 <= 분 <= 47, 0 <= 초 <= 59 의 조건을 가지고 있으며 득점 시간이 겹치는 경우는 없다.
출력
첫째 줄에는 1번 팀이 이기고 있던 시간
둘째 줄에는 2번 팀이 이기고 있던 시간을 출력한다.
실습코드
#include <bits/stdc++.h>
using namespace std;
//1.변수 목록
//골이 들어간 횟수를 적을 정수형 변수 N
//각팀당 골의 개수를 담을 정수형 변수 Lcnt,rcnt;
//각팀당 시간 및 초를 저장할 변수 Lmin,Lsec,Rmin,Rsec
int n;
int Lcnt, rcnt,Lmin,Lsec,Rmin,Rsec,prev_min,prev_sec;
string go(int a)
{
string ret = "";
if (a == 0)
ret = '0' + to_string(a);
else
ret = to_string(a);
return ret;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
int l = 0, r = 0;
string a = "";
string b = "";
cin >> a >> b;
l = Lcnt;
r = rcnt;
if (a.size() != 1 || b.size() != 5 || stoi(b.substr(0, 1)) > 47 || stoi(b.substr(3,2)) > 60)
return 0;
if (a[0] == '1')
Lcnt++;
else
rcnt++;
if (i == 0)
{
prev_min = stoi(b.substr(0, 2));
prev_sec = stoi(b.substr(3, 2));
}
if (i == n - 1)
{
if (Lcnt > rcnt)
{
//Sec가 0인경우에는 안빼줘도 된다는 조건만 추가하면 됌
if(stoi(b.substr(3, 2)) == 0)
Lmin += (48 - stoi(b.substr(0, 2)));
else
{
Lmin += (48 - stoi(b.substr(0, 2))-1);
Lsec -= stoi(b.substr(3, 2));
if (Lsec < 0)
{
Lmin -= 1;
Lsec = 60 + Lsec;
}
}
}
else
{
if (stoi(b.substr(3, 2)) == 0)
Rmin += (48 - stoi(b.substr(0, 2)));
else
{
Rmin += (48 - stoi(b.substr(0, 2)));
Rsec -= stoi(b.substr(3, 2));
if (Rsec < 0)
{
Rmin -= 1;
Rsec = 60 + Rsec;
}
}
}
}
if (Lcnt == rcnt)
{
if (l > r)
{
Lmin += (stoi(b.substr(0, 2)) - prev_min);
Lsec += (stoi(b.substr(3, 2)) - prev_sec);
if (Lsec < 0)
{
Lmin -= 1;
Lsec = 60 + Lsec;
}
else if (Lsec >= 60)
{
Lsec -= 60;
Lmin++;
}
}
else
{
Rmin += (stoi(b.substr(0, 2)) - prev_min);
Rsec += (stoi(b.substr(3, 2)) - prev_sec);
if (Rsec < 0)
{
Rmin -= 1;
Rsec = 60 + Rsec;
}
else if (Rsec >= 60)
{
Rsec -= 60;
Rmin++;
}
}
prev_min = stoi(b.substr(0, 2));
prev_sec = stoi(b.substr(3, 2));
}
}
cout << go(Lmin) << ":" << go(Lsec) << endl;
cout << go(Rmin) << ":" << go(Rsec) << endl;
}
예제 입력과 출력 다 만족하지만 어째서인지..
틀렸다고 나왔다... ㅠㅠ
아무리 생각해도 이유를 모르겠어서 결국 또 강의 실습을 봐버렸다..
강의 실습코드
#include<bits/stdc++.h>
using namespace std;
#define prev kundol
int n, o, A, B, asum, bsum;
string s, prev;
string print(int a) {
string d = "00" + to_string(a / 60);
string e = "00" + to_string(a % 60);
return d.substr(d.size() - 2, 2) + ":" + e.substr(e.size() - 2, 2);
}
int changeToInt(string a) {
return atoi(a.substr(0, 2).c_str()) * 60 + atoi(a.substr(3, 2).c_str());
}
void go(int& sum, string s) {
sum += (changeToInt(s) - changeToInt(prev));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> o >> s;
if (A > B)go(asum, s);
else if (B > A)go(bsum, s);
o == 1 ? A++ : B++;
prev = s;
}
if (A > B)go(asum, "48:00");
else if (B > A)go(bsum, "48:00");
cout << print(asum) << "\n";
cout << print(bsum) << "\n";
}
이 코드와 내 코드의 차이점은
나는 분과 초를 따로 계산하였지만, 이 코드는 초로 변환하여 저장하고 있다는 점과
나는 동점이 되는 순간, 이기는 순간이 끝났다고 가정하여서
동점일때, 이기고 있던 팀의 시간을 더해주는 방식이였는데
여기서는 상대팀의 점수가 더 높아지면 반대팀의 시간을 더해주는 방식으로 코드를 짰다.
확실히 상대팀의 점수가 더 높아지면 시간을 더해주는 방식과 시간을 초로 변환하여 저장하는 방식이 더 짧고 간결한 코드로 작성할 수 있어서 본받아야할 것 같다..!