1. 팩토리얼 - for구현

https://www.acmicpc.net/problem/10872

구현

• 그냥 2부터 N까지 for문을 돌리며
  result=1에 i를 곱했다.(1팩토리얼은 1)
• 항상 팩토리얼은 0팩토리얼을 신경써야했다.
  0! = 1;

2. 팩토리얼 0의 개수

https://www.acmicpc.net/problem/1676

구현

• 팩토리얼 문젠데 팩토리얼을 하면 안된다.
  범위를 초과한다.
• 팩토리얼을 하며 곱해야하는 수에서 2와 5의 개수를 구한다.
• 최종 10을 만들기 위해 짝을 지어야하는데, min으로 구한다.

문제점
1. for문을 이용한 팩토리얼은 아니,
그냥 팩토리얼 자체는 long long을 기준으로도 20! 밖에
담지 못한다.
2. 구현법을 생각하긴 했는데, 날 것의 코드가 된 듯하다.
일단 성공했으니 문제의 의도대로 된건가..?

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    int c2 = 0, c5 = 0;
    for(int i=1; i<=N; i++)
    {
        int n = i;

        // 2개수 확인
        while(true)
        {
            if(n%2==0)
            {
                c2++;
                n/=2;
            }
            else
            {
                break;
            }
        }

        // 5개수 확인
        while(true)
        {
            if(n%5==0)
            {
                c5++;
                n/=5;
            }
            else
            {
                break;
            }
        }
    }

    // 10을 만들기 위한 개수
    cout << min(c2, c5);

    return 0;   
}

3. GCD 합

https://www.acmicpc.net/problem/9613

구현

• 그냥 gcd 알고리즘만 구현할 수 있다면 풀린다.

문제점
1. gcd의 합을 저장하는 result값은 long long이어야 했다.
(계속 int와 long long에 의한 문제가 발생하므로..)
(그냥 long long을 default로 사용하는게 나을지도..)

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b)
{
    int c;
    while(b!=0)
    {
        c = a%b;
        a=b;
        b=c;
    }
    return a;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;

    // 테스트케이스 시작
    while(T--)
    {   
        // TC별 개수 N
        int N;
        cin >> N;

        // 벡터에 입력받기
        vector<int> arr;
        for(int i=0;i<N;i++)
        {
            int num;
            cin >> num;
            arr.push_back(num);
        }

        // 모든 쌍에 대하여 gcd를 구하고 값을 저장.
        long long result = 0;
        for(int i=0;i<N;i++)
        {
            for(int j=i+1;j<N;j++)
            {
                result += gcd(arr[i], arr[j]);
            }
        }

        // 출력
        cout << result << "\n";
    }

    return 0;   
}

4. 2진수 -> 8진수

https://www.acmicpc.net/problem/1373

구현

• 입력받은 수를 str로 보면 쉽게 풀 수 있다.
• 길이가 3으로 나누어 떨어지게 str을 수정한다.

문제점

• str로 바꾸어 보지않으면 힘듦

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

     
    string str; 
    cin >> str;
    
    while(str.length() % 3 != 0){
        str = "0" + str;
    }
 
    for(int i = 0; i<str.length(); i+=3){  
        int num = (str[i]-'0')* 4 + (str[i+1]-'0')* 2 + (str[i+2] - '0')* 1;
        cout << num;
    }

    return 0;   
}

5. 8진수 -> 2진수

https://www.acmicpc.net/problem/1212

구현

• 8진수를 2진수로 바꾸는 식만 쓸 수 있다면 쉽다.

문제점
1. 0이 입력으로 주어진 경우를 생각하지 못했다.

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    string str;
    cin >> str;

    if(str=="0")
    {
        cout << 0;
        return 0;
    }

    string result;
    for (long long i = 0; i < str.length(); i++)
    {
        result += to_string((str[i] - '0') / 4);
        result += to_string(((str[i] - '0') % 4) / 2);
        result += to_string((((str[i] - '0') % 4) % 2) / 1);
    }

    for (long long i = 0; i < result.length(); i++)
    {
        if(result[i] != '0')
        {
            cout << result.substr(i, result.length());
            return 0;
        }
    }    
}

6. 숨바꼭질

https://www.acmicpc.net/problem/17087

구현

• 거리들끼리의 gcd를 구하면 된다.
• 그게 어렵다.

문제점
1. vector를 만들어 모든 distance를 구하고,
distance끼리 가능한 모든 쌍으로 gcd를 했는데 시간초과.
2. 풀이 봤음.

#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    int c;
    while (b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, S;
    cin >> N >> S;


    int result = -1; // result의 초기값은 절대 gdcd가 될 수 없는 값으로 둔다.
    while (N--)
    {
        int n;
        cin >> n;
        
        // 입력받는 점에 대해, 시작점과의 거리를 구함.
        int distance = (S > n) ? (S - n) : (n - S);

        // result가 아무 값도 없다면, 처음 distance를 그냥 넣음.
        if(result==-1)
        {
            result = distance;
        }
        // result가 존재하면, 해당 result와 현재 distance의 gcd를 구하고,
        // gcd를 result로 둠. 3수의 gcd를 구한다면, 2수의 gcd와 나머지 1수를 gcd하면 됨.
        else
        {
            result = gcd(distance, result);
        }
    }

    cout << result;

    return 0;
}

주석 참고.
굳이 각 점끼리의 거리를 구할 필요가 없었고,
그냥 시작점과의 거리를 gcd하면 되었다.
짜피 시작점도 지나야함.

7. 골드바흐의 정석

https://www.acmicpc.net/problem/17103

골드바흐는 짝수는 홀수 소수의 합이 아니라
그냥 소수의 합으로 표현할 수 있다고 한다.

구현

• 골드바흐? 무조건 에라토스테네스

문제점
1. che에서 long long하는 것을 까먹었다.
= vector<bool>이 문제가 있다는 이상한 오류를 출력했다.
2. 골드바흐가 홀수인 소수만 되는 줄 알았다.

while (n--)
    {
        int num;
        cin >> num;

        int count = 0;
        
        // 1. 중복을 방지하기 위해, 반까지만 감
        // 2. 2도 포함이므로 2부터 시작. (만약 홀수만이면 3부터 시작)
        for (int i = 2; i <= num / 2; i++)
        {
            if (e[i] && e[num - i])
            {
                count++;
            }
        }

        cout << count << "\n";
    }

8. 소인수 분해

https://www.acmicpc.net/problem/11653

구현

• 왜 인지 모르겠다.

문제점
1. 풀이를 보았다. 그런데 왜 단순히 d++를 하는데,
d가 소수가 될 수 있을까? 왜?

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    int d = 2;
    while (n != 1)
    {
        if (n % d == 0)
        {
            n /= d;
            cout << d << "\n";
        }
        else
        {
            d++;
        }
    }

    return 0;
}

X진법 문제가 뭔가 귀찮고 재미도 없어서 3개정도 스킵..
하지만 한 번 볼 가치는 존재.

복습필요
1. 8번문제 이해 안 됨.
2. 팩토리얼은 long long을 사용해도 20이 최대이다.
3. X진수 문제 필요하다고 생각하면 더 풀기