[BOJ / 백준] 15996 팩토리얼 나누기 (S3^ / 수학) - Python

링크

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

 

 

 

 

문제 해석

입력

첫 번째 줄 : n a

  n : 팩토리얼 수

  a : 나눌 소수

 

출력

n!을 a^k으로 표현할 때 k의 값을 출력 

 

 

 

풀이 & 코드 해석

완전 탐색 방법으로는 팩토리얼을 계산하여 a로 몇 번 나누어 떨어지는지 계산하면 될 것입니다.

 

다만 숫자의 최대 범위가 2^31! 이므로 일반적인 방법으로는 절대 시간내로 구할 수 없습니다.

 

 

 

# case 1
6 5 4 3 2 1
1   1   1
    1


# case 2
10
10 9 8 7 6 5 4 3 2 1 
1    1   1   1   1
     1       1
     1


# case 3
6 3
6 5 4 3 2 1
1     1


# case 4
16 4
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
1           1          1       1
1

 

case 1을 살펴보도록 하겠습니다.

먼저 6을 2로 나눴을 때 나눠 떨어지는 수는 총 3개(6, 4, 2) 입니다.

다음 6을 4(2**2)로 나눴을 떄 나눠 떨어지는 수는 총 1개(4) 입니다.

 

 

이와 같은 방법을 다른 케이스에도 적용하면

case 2:

5개(10, 8, 6, 4, 2)

2개(8, 4)

1개(8)

 

case 3:

2개(6, 3)

 

case 4:

4개(16, 12, 8, 4)

1개(16)

을 확인할 수 있습니다.

 

즉, a, a^2, a^3, ... 과 같이 a의 제곱수에서 각각 몇 개의 수가 나누어 떨어지는지를 확인하고 이를 더하면 정답을 찾을 수 있습니다.

 

 

 

한편 문제의 질문 게시판을 들어가면 문제 제작자가 직접 풀이 과정을 설명한 내용이 나옵니다.

 

해당 문제에서 확인할 수 있는 신기한 규칙이 있는데,

 

i번째 몫의 개수를 구하기 위해 i-1번째 몫을 a^(i-1)로 나눠주면 된다는 것입니다.

 

 

 

case 1에서 2로 나누어 떨어지는 수는 총 3개였습니다.

 

다음 4(2**2)로 나누어 떨어지는 수는 3 // 2 로 1개가 나온다는 규칙입니다.

 

 

case 4에서 4로 나눠떨어지는 수는 총 4개이고,

 

16으로 나누어 떨어지는 수는 4 // 4가 되어 1개가 나옵니다.

 

위와 같은 방식으로도 해당 문제를 해결할 수 있습니다.

 

 

 

 

코드

풀이 1

n, a = list(map(int, input().split()))

aa = a
ans = 0
while aa <= n:
    ans += n // aa

    aa = aa * a

print(ans)

 

 

 

풀이 2  (출제자 풀이)

n, a = list(map(int, input().split()))

ans = n // a
now_ans = n // a

while now_ans > 0:
    now_ans = now_ans // a
    ans += now_ans

print(ans)

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java