one Book a Day

이분탐색 + bfs import sys input = sys.stdin.readline from collections import deque def is_possible(limit): queue = deque() queue.append(s) visited = {i: False for i in range(1,N+1)} visited[s] = True while queue: cur_node = queue.popleft() if cur_node == e: return True for next_node, next_limit in graph[cur_node]: if not visited[next_node] and limit

도착 가능한지 여부만 판단하면 됨. dfs import sys sys.stdin = open('input.txt') def dfs(x,y): for i in range(4): nx = x+dx[i] ny = y+dy[i] if 0

내 풀이. dfs 조합으로 무식하게 풀었다. import sys input = sys.stdin.readline def dfs(s,cnt): global ans if cnt==3: ans += 1 return if cnt > 3: return for next in range(s+1,N+1): if not eat[next] and next not in donot_list: eat[next] = True for hate in ice_cream[next]: donot_list.append(hate) dfs(next, cnt + 1) eat[next] = False for hate in ice_cream[next]: donot_list.pop() N, M = map(int, input().split()) ice..

1. deque로 직접회전 from collections import deque for _ in range(10): test = int(input()) arr = deque(list(map(int, input().split()))) cnt = 0 while arr[-1] > 0: arr.rotate(-1) arr[-1] -= cnt%5+1 cnt += 1 arr[-1] = 0 print(f'#{test}',*arr) 2. 포인터로 간접회전 for _ in range(10): test = int(input()) arr = list(map(int, input().split())) idx = -1 cnt = 0 while arr[idx] > 0: idx += 1 idx %= 8 arr[idx] -= cnt %..

1번은 재귀 분할정복이고 2번은 반복문 분할 정복이다. 1번 def power(n, p): if p == 0: return 1 # Call this only once, instead of two times. power_p_divided_by_2 = power(n, p // 2) if p % 2: return n * power_p_divided_by_2 * power_p_divided_by_2 else: return power_p_divided_by_2 * power_p_divided_by_2 2번 def power(a, n): ret = 1 while n > 0: if n % 2 != 0: ret *= a a *= a n //= 2 return ret

핵심은 power함수의 logN화. 1번 50점. import sys input = sys.stdin.readline N = int(input()) menus = sorted(map(int,input().split())) MOD = 1000000007 minus = 0 for i in range(N-1): for j in range(i+1,N): minus += ((menus[j] - menus[i])*(2**(j-i-1)))%MOD print(minus%MOD) 2번 50점 N = int(input()) menus = sorted(map(int,input().split())) MOD = 1000000007 minus = 0 plus = 0 for i in range(N): minus += (menus[..

1. 투포인터 후 큰 숫자부터 cnt 50점 통과 import sys input = sys.stdin.readline from collections import defaultdict N, M = map(int, input().split()) cards = list(map(int, input().split())) cards.append(cards[-1]) # 연속된 카드 묶기. 정확히 M개의 카드팩. 같은 종류 카드 두장되면 안됨. # 카드팩의 최대 길이. left = 0 pack_cnt = [] card_pack = defaultdict(int) for right in range(N+1): card_pack[cards[right]] += 1 if card_pack[cards[right]] > 1: pac..

그냥 바뀔때마다 센다음 작은거 +1 import sys input = sys.stdin.readline N = int(input()) s = input().rstrip() cnt = {'B': 0,'R': 0} cnt[s[0]] += 1 for i in range(1,N): if s[i] != s[i-1]: cnt[s[i]] += 1 print(min(cnt['B'],cnt['R'])+1)

이분탐색 짤때마다 느끼지만 조금 인덱싱 꼬일때가 있움.. l =(0.9)*f[m]: l = m + 1 else: r = m c += r-i-1 print(c)

마이너스로 증가하는 배열 import sys input = sys.stdin.readline from bisect import bisect_left N = int(input()) arr = list(map(int, input().split())) q = [] q.append(-arr[0]) for i in range(1,N): if -arr[i] > q[-1]: q.append(-arr[i]) else: q[bisect_left(q,-arr[i])] = -arr[i] print(N-len(q))