one Book a Day

간격 컨트롤이 아닌 내부 요소들의 합으로 컨트롤하는 슬라이딩 윈도우. import sys input = sys.stdin.readline N = int(input()) prex_sum, left = 0, 0 answer = 0 # 슬라이딩 윈도우 for right in range(1,N+1): # 결론적으로 end는 기존 슬라이딩 윈도우 처럼 일정 간격이 고정이 아니라 # 일정 합 이상이되면 알아서 그 간격이 줄어드는 시스템이므로 한번 순회로 전부 조사 가능. while left < N and prex_sum < N: prex_sum += left+1 left += 1 if prex_sum == N: answer += 1 prex_sum -= right print(answer)

배열에서 위치당 총합에 얼마나 기여하는지 보면 됨. 가에 있는 열, 행은 인덱스 0, end는 1번, 1~end-1까지는 2번 내부에 있는 열, 행은 인덱스 0, end는 2번, 1~end-1까지는 4번 이걸 기준으로 각 열 행 합에 대해 가에있는 값과 차이를 비교해주고 바꿔서 올라가면 바꿔주면 된다. import sys input = sys.stdin.readline N, M = map(int, input().split()) matrix = [list(map(int,input().split())) for _ in range(N)] # 1~M-2번 인덱스, 1~N-2번 인덱스의 합이 가장 작은 배열과 가생이에 있는 합이 가장 큰 배열과 교환을 해준다. # 열검사 -> (1~N-2)*2 + 0 + N-1 ..

가장 큰 정사각형 만들기와 동일하다. 장애물이 나오면 최소 길이가 0으로 끊기고 다시 1부터 하나씩 늘려가는방식. import sys input = sys.stdin.readline # 가장 큰 정사각형 문제와 같은 문제. 위 좌, 대각 안쪽 중 가장 변의 길이가 짧은 변에 하나를 추가시켜주는 방식이며 # 장애물을 만나면 다시 0부터 시작한다. M, N = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(M)] dp_length = [[0 for _ in range(N+1)] for _ in range(M+1)] max_length = 0 for i in range(1,M+1): for j in range..

카운팅하고 가장 숫자 큰 애들로만 만들어줌. import sys input = sys.stdin.readline n, m = map(int, input().split()) dnas = [input().rstrip() for _ in range(n)] nut = ['A','C','G','T'] dp_sum = [[0 for _ in range(4)] for _ in range(m)] for i in range(n): for j in range(m): for k in range(4): if dnas[i][j] == nut[k]: dp_sum[j][k] += 1 break result = '' cnt = 0 for i in range(m): tmp = max(dp_sum[i]) result += nut[dp_..

선호도 관리를 어떻게 할 것인가? 일단 힙으로 하긴했는데.. 최선일지는 모르겠다. import sys from heapq import heappop,heappush input = sys.stdin.readline # N일 K종류 맥주 무료 제공 # 하루 맥주 1병 전에 받은 종류 못받음. # 맥주 N개의 선호도 합 M이상. # 조합 K 종류 맥주 중 N개 추출 합이 M이상되는. # 도수 낮은거 순으로 먹음. N, M, K = map(int, input().split()) beers = [list(map(int, input().split())) for _ in range(K)] beers2 = sorted(beers,key=lambda x: (x[1],x[0])) heap = [] flav_p = 0 cn..

최대길이 회문 확인. 사실 while문보다 for문, slicing이 더 빠르다. import sys inmput = sys.stdin.readline def check(a,left,right): while left < right: if a[left] != a[right]: return 0 left += 1 right -= 1 return 1 s = input().rstrip() n = len(s) # 최대 길이가 회문 아니면 n if not check(s,0,n-1): print(n) # 최대길이에서 하나뺀게 회문 아니면 n-1 elif not check(s,0,n-2): print(n-1) else: print(-1)

기존 마나커 탐색에 1. 중심이 #이 아닐때(크기1짜리 펠린드롬) 2. 반지름 갱신시 #을 뺀 반지름의 크기만큼 펠린드롬수 추가 3. 범위 확장 시 확장된 범위가 #범위가 아니면 펠린드롬 추가 import sys input = sys.stdin.readline def manacher(string): n = len(string) a = [0] * n # i번째 문자를 중심으로 하는 가장 긴 팰린드롬 반지름 크기. c = 0 # 중심점(center) 초기화 r = 0 # 시작점에서 가장 먼 반경(펠린드롬 끝나는 인덱스중 가장 큰 값.) answer = 0 for now in range(n): if string[now] != '#': answer +=1 # i번째 문자가 now 아래쪽에 있는 문자를 중심으로 ..

마나커 알고리즘의 핵심은 #을 삽입해 짝수 펠린드롬에 대비하는것, 중심점과 반지름 a배열의 관리. a배열의 관리는 r과 현재 인덱스now값에 의거해 관리되며 r과c값은 펠린드롬 범위 내 외에서 출발지점 인덱스 0에서 얼마나 멀어졌냐에 따라 관리된다. import sys input = sys.stdin.readline def manacher(string): n = len(string) a = [0] * n # i번째 문자를 중심으로 하는 가장 긴 팰린드롬 반지름 크기. c = 0 # 중심점(center) 초기화 r = 0 # 시작점에서 가장 먼 반경(펠린드롬 끝나는 인덱스중 가장 큰 값.) for now in range(n): # i번째 문자가 now 아래쪽에 있는 문자를 중심으로 하는 팰린드롬 범위 밖의..

중복순열 문제이며 N개를 K칸에 분배하는 문제이다. K칸에서 N-1개를 분배하는 경우에서 1개를 더 분배하는 모든 경우의 수(0인칸이 남는 경우의수가 배제됨) N개를 K-1칸에 분배 하는 경우의 수에 0인칸을 하나씩 붙혀주는 경우의 수(위에서 배제된 경우의 수가 충족됨) 의 합을 구하는 문제. import sys input = sys.stdin.readline N, K = map(int, input().split()) dp = [[0]*5001 for _ in range(5001)] # 결국 숫자1 N개를 K개의 칸에 분배하는 경우의 수. # N-1개를 K개에 분배하는 경우의수에 1씩 더하는 경우 + N개를 K-1개에 분배하는 경우의수에서 0을 가지는 한칸을 더하는경우, for i in range(1,N..

늘 숫자가 있고 없고의 경계를 기준으로 값을 구할때 365일째에서 0으로 넘어가는 구간이 없기 때문에 계산이 끝나지 않을 경우가 많은데 이런경우 늘 조심.. 마지막에 한번 정산 해주거나 배열 뒤에 0값을 하나 넣어서 마무리 시켜줘야함.. import sys input = sys.stdin.readline N = int(input()) sch = [0]*(366) for _ in range(N): a, b = map(int, input().split()) for i in range(a,b+1): sch[i] += 1 area = 0 max_h = 0 for i in range(1,366): if not sch[i-1] and sch[i]: left = i if max_h < sch[i]: max_h = s..