Q www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net A 원했던 풀이가 어떤 것인지는 모르겠으나, 규칙을 파악하면 쉽게 풀 수 있다는 것을 알게 되었다. 코드 n = int(input()) if n % 2 ==0: print('CY') else: print('SK')
이진 탐색 알고리즘 Q www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net A 이진 탐색 알고리즘을 쓰는데, bisect 라이브러리를 활용하면 더 쉽게 풀 수 있다. bisect 사용 코드 from bisect import bisect_left, bisect_right import sys testcase = int(sys.stdin.readline().rstrip().split()) for _ in range(..
이진 탐색 알고리즘 파라메트릭 서치 Q www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net A 이진 탐색 문제이다. 다만, 문제를 그냥 풀기보다는 파라메트릭 서치를 적용하여 결정 문제로 바꾼 뒤에 푸는 것이 훨씬 간단해진다. 가장 인접한 두 공유기 사이의 최대 거리를 구하는 문제이므로, 최대 거리를 범위로 잡고, 공유기를 다 설치할 수 있는지 결정하는 문제로 바꿔서 풀었다. 코드 import sys n, c =..
Q www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net A 원래는 이진 탐색 알고리즘으로 푸는 문제인 것 같으나, 이진 탐색을 고민하다가 그냥 식이 떠올라서 편하게 풀었다. 코드 import sys s = int(sys.stdin.readline().rstrip()) import math n = (- 1 + math.isqrt(1 + 8 * s)) // 2 #f(x) = (x(x+1))/2 = Σx라는 걸 이용했다. print(n)
