-
백준 # 15736Algorithm 2023. 12. 7. 10:55
https://www.acmicpc.net/problem/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)
- 고찰
- 나의 풀이는 메모리 초과,,
- 모범답안의 풀이가 너무 충격적...수학적으로 접근한다면 패턴을 발견해서 한 줄만에 풀이할 수 있다
'Algorithm' 카테고리의 다른 글
[비대칭키 알고리즘] DH, RSA의 수학적 자물쇠와 그 취약점 보완 (0) 2024.04.17 코드트리 사용 후기 #2 (0) 2024.04.06 코드트리 사용 후기 #1 (0) 2024.03.02 백준 # 14568 (1) 2023.12.06 백준 #1816 (1) 2023.12.05