one Book a Day

deque와 맨앞 요소만 책임지는 front배열을 두어 운용했습니다. import sys input = sys.stdin.readline from collections import deque N = int(input()) a = list(map(int, input().split()))[::-1] floor = [i for i in range(N, 1, -1)] front = [1] q = deque() for command in a[1:]: if command == 1: q.appendleft(front.pop()) front.append(floor.pop()) elif command == 2: q.appendleft(floor.pop()) else: q.append(floor.pop()) answer ..

global 변수 안쓰고 탑다운 방식으로 구현 import sys input = sys.stdin.readline def dfs(depth, weight): if depth == N: return 1 ret = 0 for i in range(N): next_weight = weight - K + a[i] if not check[i] and next_weight >= 500: check[i] = True ret += dfs(depth + 1, next_weight) check[i] = False return ret N, K = map(int, input().split()) a = list(map(int, input().split())) check = {i: False for i in range(N)} pr..

deque로 구현했습니다. import sys input = sys.stdin.readline from collections import deque N = int(input()) q = deque([i for i in range(1, N + 1)]) while len(q) != 1: q.popleft() if len(q) == 1: break q.rotate(-1) print(q.pop())

가장 자주나오는 prefix-sum 문제 import sys input = sys.stdin.readline R, C, Q = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(R)] dp = [[0 for _ in range(C + 1)] for _ in range(R + 1)] for i in range(1, R + 1): for j in range(1, C + 1): dp[i][j] = -dp[i-1][j-1] + dp[i-1][j] + dp[i][j-1] + matrix[i-1][j-1] for i in range(Q): r1, c1, r2, c2 = map(int, input().split()) a..

나냐 전이냐. 보통 내가 1보다 크면 무조건 큰 값이 나온다. 근데 만약 1보다 작은 값이 계속되어 1 미만으로 떨어질 때 나보다 작아지면 굳이 그 연속 부분을 끌고갈 필요가 없다. import sys input = sys.stdin.readline N = int(input()) li = [float(input()) for _ in range(N)] for i in range(1, N): li[i] = max(li[i], li[i]*li[i-1]) print(f"{max(li):.3f}") 스터디 다른분이 소개해주신 카데인 알고리즘. import sys input = sys.stdin.readline N = int(input()) cur = 1 answer = 1 max_num = 0 for _ in r..

평범한 분할정복문제입니다. 3분할할때 칸막이 설치 위치만 잘 고려해주면 됩니다. import sys input = sys.stdin.readline def count_odd(n): cnt = 0 for i in n: if int(i) & 1: cnt += 1 return cnt def divided(n, cnt): global max_v, min_v s = str(n) cnt += count_odd(s) if len(s) == 1: min_v = min(min_v, cnt) max_v = max(max_v, cnt) return elif len(s) == 2: divided(n // 10 + n % 10, cnt) else: for i in range(1, len(s) - 1): for j in rang..

시와 제목을 잇고 딕셔너리에 횟수를 저장, 1씩 빼주는 식. 다음꺼랑 문자 같으면 조사 x import sys input = sys.stdin.readline poem = input().rstrip() title = ''.join([a[0].upper() for a in poem.split()]) poem += title + '.' left_space = int(input()) left_push_alphabet = {idx: cnt for idx, cnt in enumerate(map(int, input().split()))} for i in range(len(poem) - 1): if poem[i] == poem[i + 1]: continue if poem[i] == ' ': if left_space:..

좌우에 양이 얼마나 있냐? 마지막 양으로부터 얼마나떨어져있냐? 의 곱을 빈칸마다 계산해 한 빈칸 dection에서 최솟값을 구해 계산해줌 import sys input = sys.stdin.readline for test in range(int(input())): n = int(input()) arr = list(input().rstrip()) + ['.'] dp = [[0, 0] for _ in range(n + 1)] last_sheep = -1 cnt = 0 for i in range(n + 1): if arr[i] == '*': last_sheep = i cnt += 1 else: if last_sheep != -1: dp[i][0] = cnt * (i - last_sheep) last_sheep..

ai - bj = i - j를 ai - i = bj - j 로 치환시켜 dictionary에 저장 후 조합의 수만큼 더해줌. import sys input = sys.stdin.readline from collections import defaultdict for test in range(int(input())): n = int(input()) arr = list(map(int, input().split())) new_arr = defaultdict(int) for idx, num in enumerate(arr): new_arr[num - idx] += 1 answer = 0 for num in new_arr: k = new_arr[num] answer += k * (k - 1) // 2 print(an..

홀수로 대각선 반 채우고 짝수로 중앙부터 끝까지 대각선으로 채워줬습니다. import sys input = sys.stdin.readline for test in range(int(input())): n = int(input()) if n == 1: print(1) continue elif n == 2: print(-1) continue matrix = [[1] * n for _ in range(n)] k = 1 for i in range(n): for j in range(i, -1, -1): matrix[i - j][j] = k k += 2 k = 2 if n&1: for i in range(n // 2): matrix[n//2 + 1 + i][n//2 - 1 - i] = k k += 2 else: f..