one Book a Day

각 value, cnt를 축으로 둔 2차원 dp를 통해 하나씩 고르는 경우의 수를 check해주었습니다. 이전에 수확한게 왼쪽인지 오른쪽인지 각각 수확량의 최댓값을 취하며 계산해 주었습니다. import sys input = sys.stdin.readline N = int(input()) v = [0]+[int(input()) for _ in range(N)] dp = [[v[i] * N if i == j else 0 for i in range(N + 1)] for j in range(N + 1)] for left in range(1, N + 1): for right in range(left - 1, 0, -1): dp[right][left] = max(dp[right + 1][left] + v[righ..

끝에서부터 1나오면 뒤집어주면 됩니다. import sys input = sys.stdin.readline def xor(a, b): for row in range(a + 1): for col in range(b + 1): matrix[row][col] ^= 1 n, m = map(int, input().split()) matrix = [list(map(int, list(input().rstrip()))) for __ in range(n)] cnt = 0 for row in range(n - 1, -1, -1): for col in range(m - 1, -1, -1): if matrix[row][col]: cnt += 1 xor(row, col) print(cnt)

아직 EOF 다루는게 익숙하지 않다. 예외처리에 대해 공부해야 할 듯. from collections import defaultdict while True: try: a=input() b=input() alpha1=defaultdict(int) alpha2=defaultdict(int) ans='' for s in a: alpha1[s]+=1 for s in b: alpha2[s]+=1 s = [] for char in alpha1: if char in alpha2: s.append(char) s.sort() for char in s: ans += char*min(alpha1[char],alpha2[char]) print(ans) except: break

3개 -> 2개 -> 1개 각 지점마다 살수있는 만큼 사주면 된다. 주의할 점은 두번째 지점의 갯수가 세번째보다 큰경우. 이경우는 2개씩 사는 과정을 먼저 해주어야한다. import sys input = sys.stdin.readline def buy_triple(idx): global cost k = min(arr[idx: idx + 3]) arr[idx] -= k arr[idx + 1] -= k arr[idx + 2] -= k cost += 7 * k def buy_double(idx): global cost k = min(arr[idx: idx + 2]) arr[idx] -= k arr[idx + 1] -= k cost += 5 * k def buy_each(idx): global cost cost..

그리디 문제. 3개를 동시에 살수있는 만큼 사고 2개를 사고 1개를 사는 방법. 주의할 점은 두번째 지점의 갯수가 세번째보다 큰경우. 이경우는 2개씩 사는 과정을 먼저 해주어야한다. import sys input = sys.stdin.readline def buy_triple(idx): global cost k = min(arr[idx: idx + 3]) arr[idx] -= k arr[idx + 1] -= k arr[idx + 2] -= k cost += (B + 2 * C) * k def buy_double(idx): global cost k = min(arr[idx: idx + 2]) arr[idx] -= k arr[idx + 1] -= k cost += (B + C) * k def buy_each..

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

궁수를 전진시키며 bfs로 target을 찾는 방식. 모든 적을 없앴는데 탐색하는 경우만 가지치기 해주면 조금 더 빠른 로직을 짤 수 있을 것 같다. 하지만 지금코드도 충분히 직관적이고 깔끔하기 때문에 마무리. import sys input = sys.stdin.readline from collections import deque from heapq import heappush def search_target(x, y): if enemies[x][y]: return (x, y) q = deque() q.append((x, y)) visited = [[False] * M for __ in range(N)] visited[x][y] = True target_candidate = [] for __ in ran..