dojini 님의 블로그

문제풀이정렬금액 낮은 순금액 같을 시 index 큰 순H = 공평히 낼 수 있는 금액W = 금액을 감당할 수 있는 사람p 에서 H * W 만큼 삭감H를 줄인 후 다시 연산(H의 인원이 모두 공평하게 돈을 낼 수 있을 만큼 왼쪽부터 배제)p가 0이 될 때 까지 반복if p=3코드import sysip = lambda:map(int, sys.stdin.readline().split())T, *_ = ip()for _ in range(T): p, n = ip() f = ip() # [인덱스, 최대금액, 최대금액(연산용)]으로 저장 arr = [[idx, n, n] for idx, n in enumerate(f)] # 금액 낮은 순 정렬 # 같은 금액 당 높은 인덱스 순 정렬 ..

int의 자료구조는 Python 3.11까지는 PyVarObject의 형태였으나 Python 3.12 부터 PyObject로 변경되었다.이 글은 Python 3.13을 기준으로 제작되었다.PyLongObjectPyLongObject는 int 자료형의 구조체이다.// Include/cpython/longintrepr.h// line 93typedef struct _PyLongValue { uintptr_t lv_tag; /* Number of digits, sign and flags */ digit ob_digit[1];} _PyLongValue;// line 98struct _longobject { PyObject_HEAD _PyLongValue long_value;};_PyLong..

문제풀이다음과 같은 형태의 수열이다.쿼리 1쿼리 탐색 길이 n 내에서 계산한다.다음과 같이 3개의 구역으로 나누어 계산한다.$$an + d*n(l-1) + n(n-1)/2= a*n + d{n(l-1) + n(n-1)/2)$$쿼리 2d증가에 따라 최대 공배수의 변화가 없다.그러니 a와 d의 최대 공배수가 탐색할 공차 수열의 최대 공배수 이다.물론 탐색할 수열의 길이가 1이면 최대 공배수는 수열의 값이다.import sys, mathip = lambda:map(int, sys.stdin.readline().split())a, d = ip()q, *_ = ip()g = math.gcd(a,d)for _ in range(q): oper, l, r = ip() # 쿼리 1 if oper == 1:..

CallableCallable은 Python에서 호출 가능한 객체의 표현 타입이다.객체가 호출 가능한지는 callable 함수를 통해 확인 할 수 있다.# Callable Oprint(callable(print))# Callable Xprint(callable(1))결과TrueFalse __call__객체를 호출하였을 경우 실핼되는 함수는 객체의 magic method인 __call__이다.객체의 call 함수는 객체의 type에 명시되어 있다.print(print.__class__.__dict__["__call__"])결과 CPython의 call과 callableCPython의 type objectstruct _typeobject { PyObject_VAR_HEAD ... ternar..

문제풀이임의의 가로등 A를 기준으로 모든 가로등 N이 (Ax, Ny) & (Nx, Ay)를 만족하면 Balance가 잡혀있다.시간복잡도는 case당 dict에 저장(200,000) + A를 기준으로 완전탐색(200,000) = 400,000 정도이다.case느 최대 5개로 2,000,000 정도이니 제한시간 0.5초를 가볍게 통과 할 수 있다.import sys, mathip = lambda:map(int, sys.stdin.readline().split())T, *_ = ip()for _ in range(T): N, *_ = ip() arr = [tuple(ip()) for _ in range(N)] m = {} # 가로등을 dict에 저장 for i in range(N): ..

문제풀이제곱수를 구한 후 제곱수의 배수를 배제하면 된다.제곱수를 구하려면 소수를 구하면 된다.소수를 구하는 방법은 에라토스테네스의 체를 사용한다.소수를 구하는 범위는 $\sqrt max$이다.import sys, mathN, M = map(int, sys.stdin.readline().split())# 소수 배열prime=[True]*(ms:=(math.floor(math.sqrt(M))+1))# 제곱ㄴㄴ 수 배열 arr = [True]*(M-N+1)# 마지막 소수lp = 2# M의 제곱근만큼 반복for i in range(2, ms): if not prime[i]: continue # 소수 판별 for j in range(lp, i): if i % j == 0:..

문제풀이dp[x][y] = 게임판[x][y]에서 찾을 수 있는 경로 수dp[N-1][N-1] = 1import sysip = lambda:map(int, sys.stdin.readline().split())n, *_ = ip()arr = [list(ip()) for _ in range(n)]dp = [[None]*n for _ in range(n)]dp[n-1][n-1] = 1def dfs(x, y): if dp[x][y] != None: return dp[x][y] g = arr[x][y] # 0일 경우 탐색 종료 if g == 0: return 0 r = 0 if x + g