매일 문제 풀기 - 8월 셋째 주

8/15. 영화감독 숌 (백준 1436번)

 

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

 

#python

n = int(input())
count = 0
num = 0

while count < n :
    check = 0
    num += 1
    qu = num
    is666 = False

    while True :
        re = qu % 10
        qu = qu // 10
        
        if re == 6 :
            check += 1
        else :
            check = 0

        if check >= 3 :
            is666 = True
        
        if qu == 0 :
            break
    
    if is666 :
        count += 1

print(num)

 

처음에는 규칙을 찾으려고 했다. 도저히 숫자를 1부터 시작해서 하나하나 체크하기에는 시간 초과가 나올 것 같았기 때문이었다. 근데 진짜 경우의 수까지 나오고 맨 앞에 0이 나오는 경우랑 세면서 중복되는 경우까지 전부 고려해줘야 하고 암튼 진짜 머리가 터지겠는 거임... 그래서 좀 찾아보니 이 문제는 사실 시리즈물이고 영화감독 숌 1, 2, 3, 4 까지 있었다. 그리고 1 이후의 골드, 플래티넘 문제들이 아마 그렇게 규칙을 찾아서 풀어야 되는 문제들이 아닐까.. 싶다. 이 문제는 알고리즘 분류에 브루트포스라고 적혀있기도 했고 실버5이니까 (심지어 시간 제한도 2초이다.) 하나하나 체크해가며 푸는 문제가 맞는 듯 하다. 굉장히 비효율적인 코드 같지만... 몰라 풀었으니까~~ (정답)

참고로 대충 이런식으로 하다가 때려쳤다...

 

---

 

8/19. 팩토리얼 0의 개수 (백준 1676번)

 

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

 

#python

n = int(input())
fact = 1
count = 0

for i in range (2, n+1) :
    fact *= i

while True :
    rem = fact % 10
    fact = fact // 10
    
    if rem != 0 :
        break
    else :
        count += 1

print(count)

 

뭔가 생각해서 풀어야 하나 했는데 그냥 그대로 코드로 표현만 하면 되는 문제였다. (정답)

 

---

 

8/19. 소수 찾기 (백준 1978번)

 

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

 

#python

import sys

n = int(input())
data = list(map(int, sys.stdin.readline().split()))

count = 0

for i in range (0, n) :
    isPrime = True
    for j in range (2, data[i]//2 + 2) :
        if data[i] % j == 0 :
            isPrime = False

    if data[i] == 1 :
        count += 0
    elif data[i] == 2 or isPrime :
        count += 1

print(count)

 

규칙에서 예외가 될 수 있는 경우들(1, 2, 3 같은 작은 수)을 잘 생각해야 하는 문제인 것 같다. (정답)