[CLASS 3]백준 1676번, 2579번

1676번 : 팩토리얼 0 의 개수

 

상당히 쉬운 문제이다. 일단 팩토리얼을 그냥 구하고 10으로 나누는 방법을 쓰면 무조건 시간 초과를 맞을 것이다. 그러므로 모두 더하는 방식이 아닌 다른 방식을 사용했다.

 

내 코드:

def zeroCount(n):
    f = 0
    t = 0
    for i in range(n,0,-1):
        k = i
        while k % 5 == 0 or k % 2 == 0:
            if k % 5 == 0:
                k //= 5
                f += 1
            if k % 2 == 0:
                k //= 2
                t += 1
    
    return min(f,t)

print(zeroCount(int(input())))

 

이렇게 각각 f와 t 변수에 곱하는 모든 수의 소인수 중 5와 2의 개수를 저장한 뒤 마지막에 그중 크지 않은 값을 반환하는 방법으로 풀 수 있다.

 

그리고 다 풀고 맞은 분들의 코드를 봤는데 훨씬 더 획기적인 방법이 있었다.

 

팩토리얼의 특성상 수가 5 증가했다면 그 안에는 무조건 소인수 2가 포함되어 있다.

 

즉 2와 5을 셀 필요 없이 5일때만 세주면 2는 자동으로 따라온다는 말이다.

 

그리고 25 일때는 5가 2개 추가되고, 125일때는 5가 3개 추가된다. 문제에서 입력하는 최대 수가 500 이라고 했으니 500이하의 5의 제곱수일때만 생각해주면 된다.

 

그러면 딱 두줄로 코드를 작성할 수 있다.

 

n = int(input())
print(n // 5 + n // 25 + n // 125)

 

캬~

 

2579번 : 계단 오르기

 

보자마자 dp문제라는것은 알아챘는데, 어떻게 구현해야할지 생각을 너무 오래 했고, 그래서 결국 검색했다 ㅠㅠ

 

일단 dp테이블에는 '해당 계단까지 오는데 가능한 가장 큰 합'을 저장한다. 각 계단에서 그 값은, 한칸을 건너뛰는 경우를 '점프'라고 부를때,

 

3칸 전에 '점프'하고 1칸 전에 도달한 뒤 한칸 올라온 경우

 

혹은

 

2칸 전에 '점프'를 통해 바로 올라온 경우

 

로 나뉘어진다. 이 2개를 생각해내는게 너무 어려웠던 것 같다. 자꾸 3가지 이상의 경우로 나누려 했고 그래서 더 복잡해져서 문제를 풀지 못한 것 같다.

 

이를 적용하여 다음과 같은 코드를 작성했다.

 

내 코드:

import sys
input = sys.stdin.readline

stairs = [int(input()) for _ in range(int(input()))]
if len(stairs) < 3:
    print(sum(stairs))
    exit()
dp = [stairs[0],stairs[0]+stairs[1],max(stairs[0]+stairs[2],stairs[1]+stairs[2])] + [0] * (len(stairs)-3)
for i in range(3,len(stairs)):
    dp[i] = max(dp[i-3]+stairs[i-1]+stairs[i],dp[i-2]+stairs[i])

print(dp.pop())

 

일단 입력이 1 혹은 2라면 모든 계단의 값을 합쳐서 출력하면 된다. 3 이상이라면 일단 dp테이블에 3개의 값을 저장해놓고 for문과 max함수를 통해 dp테이블을 채워나가면 된다.