one Book a Day

좌우에 양이 얼마나 있냐? 마지막 양으로부터 얼마나떨어져있냐? 의 곱을 빈칸마다 계산해 한 빈칸 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..

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')

문제의 핵심은 결국 에어컨으로부터 얼만큼의 거리에 있는가? 입니다. 백준의 최대 직사각형 만들기, SWEA의 수영장 가자 와 동일한 문제로 dp를 이용해 방해물이 없으면 기존값에서 거리값을 늘려가며 기록해주되 방해물(나보다 작은 온도의 에어컨)이 나타나면 그값에서 부터 다시 거리값을 기록해줍니다. 본 풀이는 좌, 우 다른 dp를 사용했으나 경험상 dp하나로도 구현할 수 있습니다. import sys input = sys.stdin.readline for test in range(int(input())): input() n, k = map(int, input().split()) a = list(map(lambda x: int(x) - 1, input().split())) t = list(map(int, i..

앞전의 이진수에서 1이 있는 자릿수를 계승하는 수열을 growing sequence라 하고 그렇지 않은 수열을 xor연산을 통해 growing sequence로 만들어 주는 수열을 Co-growing Sequence라 합니다. 전에 있는 값을 pivot으로 가져가야할 1의 위치를 저장하는 기준값으로 정하고 pivot에는 1이 있는데 현 수열의 값에는 없다면 Co-growing Sequence가 그만큼의 값을 가져가게끔 코드를 짰습니다. import sys input = sys.stdin.readline for test in range(int(input())): n = int(input()) x = list(map(int, input().split())) pivot = x[0] y = [0] * n for..

영어 독해가 매우 힘들었던 문제입니다. 이 문제는 열 추가와 열 조회로 나뉩니다. 지금 조회할 수 없는 열을 조회하면 불가능한 command로 판단하면 됩니다. 앞에서부터 0을 while로 넣어주고 그 후 0이 아닌값의 가능여부를 검사해 넣어주는 전략입니다. import sys input = sys.stdin.readline for test in range(int(input())): input() k, n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) answer = [] idx_a = 0 idx_b = 0 while idx_a < n and not a[idx_a]: ..

a부터 좌우로 하나씩 연속되는 알파뱃을 붙혀가는 규칙. s가 규칙으로 만들어진 문자열이면 YES를 출력. 얼마전 현대모비스 알고리즘 대회 2번?의 열화판 당시는 deque로 풀었지만 이번에는 twopointer로 양끝에서부터 한 규칙씩 거슬러 올라가 마지막에 a가 남는 것까지 확인하는 전략을 세웠습니다. 최초 시작은 start로 총 문자열 길이에서 소문자 a의 아스키코드 넘버만큼 더해주고 a를 제외하는 의미에서 1을 빼주면 마지막 문자의 아스키코드 넘버가 됩니다. 거기서부터 확인해주면 됩니다. import sys input = sys.stdin.readline for test in range(int(input())): s = input().rstrip() left = 0 right = len(s) - 1..

점 a에서 b까지의 최소거리를 구하는 문제. 방해물 f가 한개 존재하지만 한개로는 무수히 많은 path를 방해할 수 없다. 방해 가능한 경우의 수는 a와 b와 f가 일직선상에 존재하고 f 가 두 점 사이에 있을 때. 이경우만 예외처리해서 +2 해주면 된다. import sys input = sys.stdin.readline for test in range(int(input())): input() a_x, a_y = map(int, input().split()) b_x, b_y = map(int, input().split()) if a_x < b_x: a_x, b_x = b_x, a_x if a_y < b_y: a_y, b_y = b_y, a_y f_x, f_y = map(int, input().split..