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] *..

확률을 인자로 넘기는 백트래킹. 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..

union- find를 통해 집합을 나누고 group의 크기를 측정해 출력해줬습니다. def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] def union(x, y): x = find(x) y = find(y) if x > y: x, y = y, x parents[y] = x for test in range(1, int(input()) + 1): N, M = map(int, input().split()) prefer_set = list(map(int, input().split())) parents = {i: i for i in range(1, N + 1)} for i in range(M): a, ..

백준의 유명한 bfs 시리즈인 숨바꼭질 시리즈의 일종. 쓸데없는 visited 배열 할당을 없애기위해 set으로 관리했는데 나쁘지 않은 것 같다. from collections import deque def bfs(start): q = deque() q.append((start, 0)) visited = set() visited.add(start) while q: cur_node, cnt = q.popleft() for next_node in (cur_node + 1, cur_node - 1, cur_node * 2, cur_node - 10): if next_node

최소 배열 합 문제와 완전히 동일한 백트래킹 문제입니다. def dfs(depth, total): global min_sum if depth == N: min_sum = min(min_sum, total) return if total > min_sum: return for next_node in range(N): if not col_check[next_node]: col_check[next_node] = True dfs(depth + 1, total + matrix[depth][next_node]) col_check[next_node] = False for test in range(1, int(input()) + 1): N = int(input()) matrix = [list(map(int, input(..

dp로 뒤에서부터 최솟값을 가져와 0까지 역산했습니다. for test in range(1, int(input()) + 1): N, *battery = map(int, input().split()) dp = [float('inf')] * N dp[N - 1] = 0 for i in range(N - 1, -1, -1): for j in range(i - 1, -1, -1): if j + battery[j] >= i: dp[j] = min(dp[j], dp[i] + 1) print(f'#{test} {dp[0] - 1}')