글 읽기 - C++ 이거 왜 틀렸을까요??

rms8hszi 1년 전 0

소인수분해해서 2랑 5개수 센 다음에 팩토리얼식에서 나올 수 있는 (2 ^ n) * (5^ n) 경우의 수 다 센거 같은데 왜 틀렸을까요??

혹시 반례가 있을까요..?

#include <iostream>

int main() {
    int Number = 0;
    std::cin >> Number;
    // N을 입력받음
    int Number_2 = Number;
    int Number_5 = Number;
    int Counter_2 = 0;
    int Counter_5 = 0;
    while (Number_2 % 2 == 0) {
        Number_2 = Number_2 / 2;
        Counter_2++;
    }
    while (Number_5 % 5 == 0) {
        Number_5 = Number_5 / 5;
        Counter_5++;
    }
    // N을 소인수분해하여 2와 5가 몇 개 곱해져있는지 확인
    int Counter_0 = 0;
    for (int i = 1; i <= Counter_2; i++) {
        for (int j = 1; j <= Counter_5; j++) {
            if ((2 ^ i) * (5 ^ j) >= 100) {
                Counter_0 += 2;
            }
            else {
                Counter_0++;
            }
        }
    }
    if (Counter_2 > 0 && Counter_5 > 0) {
        Counter_0++;
    }
    // 팩토리얼 전개식에 곱해져 있는 10의 개수를 확인
    std::cout << Counter_0 << std::endl;
}

djm03178 1년 전 1

C++에서 ^는 제곱이 아니라 비트 XOR 연산자입니다.

wnsgus821 1년 전 2

맨 처음 입력받은 Number 자체에 대해서만 2의 지수, 5의 지수를 찾으려고 하시는데,

문제는 N! = 1 × 2 × 3 × ˑ ˑ ˑ × N 을 다루므로, 팩토리얼 내의 모든 항 각각에 대해서 지수 카운팅을 한 후 더해줘야합니다.

추가적으로, 주어진 N 팩토리얼에서 2의 지수, 5의 지수를 카운팅 합을 구하시게 된다면

주어진 입력값 N (0 <= N <= 500) 에서 항상 2의 지수의 합 >= 5의 지수의 합이 성립함을 알 수 있습니다.

쉽게 설명하자면, 5의 배수는 5, 10, ˑ ˑ ˑ 로 나타나는데, 2의 배수는 2, 4, 6, 8, 10, ˑ ˑ ˑ 이런식으로 나와서 따라잡을 수 없습니다.

이 말은 즉, 10을 만들 때 5와 함께 합쳐질 2가 항상 있음을 보증할 수 있다는 겁니다.

그래서 5의 지수만 카운팅 해주셔도 됩니다.

rms8hszi 1년 전 0

앗 해결되었습니다! N에서 1씩 줄여가면서 5의 지수 찾으니까 제대로 나오네요! 정말 감사합니다!!

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

문제

문제

출처

ICPC

C++ 이거 왜 틀렸을까요??

rms8hszi 1년 전 0

djm03178 1년 전 1

wnsgus821 1년 전 2

rms8hszi 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말