백준 # 15736

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

15736번: 청기 백기

 

• 나의 풀이

n = int(input())
answer = 0
flags = [0] * n

# n명이 n개의 깃발을 각 순서의 배수만큼 뒤집은 결과 리스트 
for i in range(1, n+1):
  for j in range(1, n+1):
    if j*i < n:
      flags[j*i] += 1

# 백색 깃발의 개수 구하기
for flag in flagss:
  if flag % 2 != 0: # 홀수 번 뒤집었을 때 백색 깃발
    answer += 1
print(answer)

 

• 모범 답안
  • 패턴을 발견해보자!
    
    • n 이하의 가장 큰 제곱수를 구하면 된다

	1	2	3	4	5	6	7	8
최초 깃발 상태	o	o	o	o	o	o	o	o
1번 학생이 깃발을 뒤집은 상태	x	x	x	x	x	x	x	x
2		o		o		o		o
3			o			x
4				x				x
5					o
6						o
7							o
8								o

n = int(input())
answer = int(n**0.5)
print(answer)

 

 

• 고찰
  • 나의 풀이는 메모리 초과,,
  • 모범답안의 풀이가 너무 충격적...수학적으로 접근한다면 패턴을 발견해서 한 줄만에 풀이할 수 있다