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)
이진 탐색 알고리즘 Q www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net A 이진 탐색 알고리즘을 사용하였다. 코드 import sys from math import floor x, y = map(int, sys.stdin.readline().rstrip().split()) z = floor((y*100)/x) #내림 start = 0 end = 1000000000 if x == y or z == 99: #승률 100프로와 99프로는 변하지 않으므로 -..
정렬 알고리즘 Q www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net A 문제를 바로 풀려고 하지말고, 어디 위치일 것인지 예상해보고 그 위치가 입력된 리스트로 어떻게 표현해낼수 있을지 생각해보며 풀자! 코드 import sys n = int(sys.stdin.readline().rstrip()) array = list(map(int, sys.stdin.readline().rstrip().split())) array.sort() #오름차순 정렬 if n % 2 == 0: #집의 개수가..
정렬 알고리즘 Q www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net A 입력을 문자열로 받았고, key = lambda x : (-x[1], x[2], -x[3], x[0]) 를 하기 위해서 국어점수, 영어점수, 수학점수를 int로 정수형으로 변환시켰다. 입력이 10만 이상이라면 input보다 sys쓰는 습관을 들이자! 시간 10배정도 차이난다. 코드 import sys n = int(sys.stdin.readline().rstrip())..
