one Book a Day

2진수는 1 shifting으로 비트체크 후 경우의 수를 후보군 set에 넣어두었고 3진수는 k를 인덱스의 역방향으로 설정하여 연산한 숫자가 후보군 안에 있는지 확인했습니다. for test in range(1, int(input()) + 1): binary, tri = input(), input() init_binary, init_tri = int(binary, 2), int(tri, 3) target_candidate = set() for i in range(len(binary)): if init_binary & (1

set으로 정답이 될수있는 경우를 찾아주면 됩니다. 사실 16칸밖에 되지 않으므로 16자리 bit를 인자로 넘겨주거나 3차원 배열(x, y, bit상태)을 만들어 bit상태와 현재num이 같으면 더 조사하지 않게 가지치기를 할 수 있습니다. 근데 안해도 통과되긴 합니다. def dfs(cnt, x, y, num): global answers if cnt == 7: answers.add(num) return for dx, dy in delta: nx, ny = x + dx, y + dy if 0

문제 이름대로 쉬운 거스름돈 문제입니다. 기본적인 그리디문제입니다. for test in range(1, int(input()) + 1): N = int(input()) units = [50000, 10000, 5000, 1000, 500, 100, 50, 10] unit_cnt = [0] * 8 for i in range(8): if N >= units[i]: cnt = N // units[i] unit_cnt[i] += cnt N %= units[i] print(f'#{test}') print(*unit_cnt)

적힌 숫자가 중복 없이 1씩 늘어나기 때문에 배열에 index로 쓸 수 있습니다. 그 후 index에 따라 이동 가능여부를 조사해주면 됩니다. 올해 하반기 라인 코테 3번 문제와 아이디어가 비슷합니다. for test in range(1, int(input()) + 1): N = int(input()) dp = [0] * (N ** 2 + 1) for i in range(N): row = list(map(int, input().split())) for j in range(N): dp[row[j]] = (i, j) delta = ((0, 1), (1, 0), (0, -1), (-1, 0)) max_length, cnt, start, answer = 1, 1, 1, 1 for num in range(1, l..

dfs로 백트래킹하며 최솟값을 갱신해주는 로직입니다. 높이가 '이상' 임이 명확히 주어져있어서 수월했습니다. def dfs(u, total): global min_val if total >= B: min_val = min(min_val, total) for v in range(u + 1, N): if not visited[v] and total + s[v] < min_val: visited[v] = True dfs(v, total + s[v]) visited[v] = False for test in range(1, int(input()) + 1): N, B = map(int, input().split()) s = list(map(int, input().split())) visited = [False] *..

투포인터를 각 출발선마다 돌리는 로직입니다. 정렬후 앞에서 하나씩 고정값으로 픽스시켜두고 두가지 포인터로 합의 범위를 0으로 수렴시켜나가는 과정입니다. import sys input = sys.stdin.readline n = int(input()) liquid = sorted(list(map(int, input().split()))) close_zero = float('inf') selected = [0]*3 for start in range(n - 2): left, right = start + 1, n - 1 while left < right: sum_value = abs(liquid[start] + liquid[left] + liquid[right]) if sum_value < close_zero:..

트리의 지름 문제. bfs 두번을 통해 최대 거리를 두번 산출해주면 된다. 조금 중요한게 graph배열을 1부터가 아니라 0부터 만들어 주어야 한다는점. (노드가 1개일때 내가 노드를 1로 설정해둬서.. 지금보니 그냥 target_node를 1로 설정해 주었다면 1부터 해도 될것같다) import sys input = sys.stdin.readline from collections import deque def bfs(start): q = deque() q.append((start, 0)) visited = [False for __ in range(10001)] visited[start] = True max_dist = 0 target_node = 0 while q: cur_node, cur_dist =..

확률을 인자로 넘기는 백트래킹. def dfs(row, p): global max_p if row == N: max_p = p return for col in range(N): next_p = p * P[row][col] if not col_check[col] and next_p > max_p: col_check[col] = True dfs(row + 1, next_p) col_check[col] = False for test in range(1, int(input()) + 1): N = int(input()) P = [list(map(lambda x: int(x) / 100, input().split())) for __ in range(N)] col_check = [False] * N max_p = 0..

숫자의 순서가 정해져 있으므로 greedy하게 풀면 된다. import sys input = sys.stdin.readline N , K = map(int,input().split()) nums = list(input().rstrip()) answer = [] for i in range(N): while K != 0 and answer: if answer[-1] < nums[i]: answer.pop() K -= 1 else: break answer.append(nums[i]) if K: answer = answer[:-K] print(''.join(answer))

책을 순서대로 쌓으므로 그디리하게 풀어야합니다. import sys input = sys.stdin.readline N, M = map(int, input().split()) weights = list(map(int, input().split())) box, cnt = M, 1 for weight in weights: if box - weight >= 0: box -= weight else: cnt += 1 box = M - weight if not N: cnt = 0 print(cnt)