백준 - 15736(청기 백기, 파이썬)

 

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

15736번: 청기 백기

문제 접근

• 문제 자체는 매우 간단하지만 입력 값이 높아 규칙을 발견해서 시간 초과를 해결하는 문제

 

초과나는 코드

# 초기의 깃발은 모두 청색?
# 1. 일단 완전탐색으로 구현해보기 -> 시간초과 날것임
n = int(input())
# 0은 청, 백은 1
flag = [0] * (n+1)
flag [0] = 10
for i in range(1, n+1):
    for j in range(i, n, i):
        if flag[j] == 0:
            flag[j] = 1
        elif flag[j] == 1:
            flag[j] = 0

print(flag.count(1))

안되는건 알지만 그냥 한 번 만들어봤다. 이제 규칙을 파악해보자

 

정답 코드

n = int(input())
# 이 문제는 제곱근을 구하는 문제였음
answer = int(n **0.5)
print(answer)

값을 일일히 대입해보니 정답들이 주어진 정수의 제곱근이라는 공통점이 있었다.