one Book a Day

1. 아랫자리수 * 9 2. 맨앞자리수 - 1 3. 맨앞자리수 * 숫자길이 보다 크면 1개추가 import sys input = sys.stdin.readline for test in range(int(input())): n = int(input()) tmp = n k = 0 while tmp // 10: tmp //= 10 k += 9 num = str(n) k += int(num[0]) - 1 if num >= num[0] * len(num): k += 1 print(k)

연속되지 않으면서 같은 문자가 나오면 NO import sys input = sys.stdin.readline for test in range(int(input())): n = int(input()) a = list(input().rstrip()) char_set = {a[0]: True} for i in range(1, n): if a[i - 1] != a[i]: if a[i] in char_set: print('NO') break else: char_set[a[i]] = True else: print('YES')

dfs로 각 순열의 카드 순서를 맞춰가며 카드를 2장씩 뒤집는 로직. 백트래킹, dijkstra로 최단 거리 측정. shift이동은 ctrl_move로 for문 이용. from collections import defaultdict from heapq import heappush, heappop from itertools import permutations def solution(board, r, c): def ctrl_move(x, y, dx, dy, visited): for i in range(1, 4): nx, ny = x + dx * i, y + dy * i if (nx, ny) in visited and not visited[(nx, ny)]: return (nx, ny) if dx == 1 a..

강의실 배정문제. 여러번 풀었던 문제. 방을 몇개 가져갈꺼냐? 끝난시간이면 빼고 갈아끼워준다. import sys input = sys.stdin.readline from heapq import heappop, heappush n = int(input()) heap = [] count = 0 for _ in range(n): num, start, end = map(int, input().split()) heappush(heap, [start,end,num]) classroom = [] start, end, num = heappop(heap) heappush(classroom, end) while heap: start, end, num = heappop(heap) if classroom[0]

parametric search로 원하는 갯수로 나눌 수 있는 최대 길이를 탐색 import sys input = sys.stdin.readline M, N = map(int, input().split()) L = list(map(int, input().split())) start, end = 1, max(L) answer = 0 while start = M: answer = target_l start = target_l + 1 else: end = target_l - 1 print(answer)

등차수열로 속도가 증가했을 때 k번째 돌에서 a만큼의 최대 속도를 가질 수 있고 이는 k = a(a+1)/2 를 만족한다. 정리하면 a = sqrt(2 * k + (1/4)) - 1/2 이기 때문에 i번 위치에서 int(sqrt(2 * i)) + 1까지 검사하면 가능한 모든 속도에서의 값을 조사할 수 있다. import sys input = sys.stdin.readline N, M = map(int, input().split()) dp = [[float('inf')] * (int((2 * N)** 0.5) + 2) for _ in range(N + 1)] dp[1][0] = 0 stones = set([int(input()) for _ in range(M)]) for i in range(2, N + 1..

dfs 백트래킹 했는데 dp로 상태인자 주고 하는게 더 나았을지도 import sys input = sys.stdin.readline def dfs(node, energy, key): global min_energy if energy >= min_energy: return if node == N: min_energy = min(min_energy, energy) return if node + 1

풀이 1. 극소점부터 큰값이 나올때마다 그만큼 채워주면서 연산. import sys input = sys.stdin.readline n = int(input()) cnt = 0 stack = [int(input())] max_num = stack[-1] for _ in range(n - 1): num = int(input()) if stack[-1] < num: cnt += num - stack[-1] max_num = max(max_num, num) stack.pop() stack.append(num) cnt += max_num * len(stack) - sum(stack) print(cnt) 풀이2. 분할정복으로 max_idx를 pivot으로 좌우 분할 해 각 구간의 연산값을 더해주며 최상단까지 올라..

쭉 가면서 계속 바꿔주면 된다. 아니면 누적 배열을 만들어 바꾼 횟수를 기록해주며 홀짝 판별해도 되는데 소요가 비슷하기 때문에 그냥 그리디로 계속 바꾸는게 낫다. import sys input = sys.stdin.readline N, M = map(int, input().split()) A = [list(map(int, list(input().rstrip()))) for _ in range(N)] B = [list(map(int, list(input().rstrip()))) for _ in range(N)] cnt = 0 for i in range(N): for j in range(M): if i < N - 2 and j < M - 2: if A[i][j] != B[i][j]: for x in rang..

hash map으로 index 저장해뒀다가 query 들어오면 반환 import sys input = sys.stdin.readline a_idx = {} N, M = map(int, input().split()) A = sorted([int(input()) for _ in range(N)]) for i in range(N): if A[i] not in a_idx: a_idx[A[i]] = i D = [int(input()) for _ in range(M)] for num in D: if num in a_idx: print(a_idx[num]) else: print(-1)