one Book a Day

구현을 처음풀때는 막막했지만 브루트포스에 대해 알고난 이후로 어렵게 느껴지지는 않는 문제. 이제는 왜 골드5인줄 알겠다. 벽을 어떻게 고를 것인가? 여유공간은 어떻게 산출할 것인가? import sys input = sys.stdin.readline from itertools import combinations from collections import deque def bfs(walls): q = deque() visited = [[False]*M for _ in range(N)] ret = 0 for wall in walls: i, j = wall lab[i][j] = 1 for v in virus: x, y = v q.append((x,y)) visited[x][y] = True while q: x..

중복조합 서로다른 n개의 원소 중, 중복을 허락하여 r개를 뽑는 것. nHr = (n+r-1)C(r) 조합에서의 중복만 허용하므로 순서는 여전히 상관하지 않는다.(조합) dfs에서 i+1이 넘어가면 조합, i가 넘어가면 중복조합 def dfs(idx, depth): if depth == r: print(*comb) for i in range(idx,n): comb[depth] = arr[i] dfs(i, depth + 1) n-1개의 칸막이를 뽑아야하는 요소들 r개 사이에 배치하는 경우의 수. = n-1개의 막대기로 구분된 영역에 요소를 집어넣는 경의의 수. nHr = n-1+r C n-1 = n-1+r C r 다음에 예제 풀어 첨부할 것.

https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net fireball data를 어떻게 다룰것이냐? 나는 deque를 써서 반복문을 진행했고 중간에 이동연산은 dictionary를 이용해 각 속성을 모아줬다. 한번에 통과. import sys input = sys.stdin.readline from collections import deque def bfs(): cnt = 0 while fireballs: fi..

dfs로 통과시키긴 했는데 다른분들 답보니 그냥 w/리프노드의 수 이게 답이더라. 생각해보니 내 답도 결국 (총 물의 양)/(리프노드의 수) 이거였는데.. 통과된게 신기할 따름.. import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def dfs(cur_node, water): visited[cur_node] = True n = len(tree[cur_node])-1 if not n: ans.append(water) return unit = water/n for next_node in tree[cur_node]: if not visited[next_node]: dfs(next_node,unit) N, W = map(int, input()..

파라매틱 서치. k번 이상 자를 수 있는지 결정하는 문제. 자주나오는데 아직 좀 사고가 더디다. import sys input = sys.stdin.readline def is_minimum(mini): left = 0 cnt = 0 for right in cut_points: if right - left >= mini: left = right cnt += 1 if cnt > k: return True return False N, M, L = map(int, input().split()) cut_points = [int(input()) for _ in range(M)] + [L] for _ in range(N): k = int(input()) # M개의 지점 중 k개 선택. 사잇값의 최솟값이 가장 큰. ..

정렬해 작은 순으로 먹으면 되는 간단한 문제. import sys input = sys.stdin.readline N, L = map(int, input().split()) h_arr = list(map(int, input().split())) h_arr.sort() for h in h_arr: if L >= h: L += 1 continue break print(L)

냅색문제고 dp로 풀었습니다. import sys input = sys.stdin.readline for _ in range(3): N = int(input()) coins = {} target = 0 for _ in range(N): a, b = map(int, input().split()) coins[a] = b target += a*b if target&1: print(0) continue target //= 2 dp = [1] + [0] * (target) for coin in coins: for money in range(target,coin-1,-1): if dp[money-coin]: for j in range(coins[coin]): if money + coin*j

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net LCS에서 연속성만 부여하면 된다. 같을때 대각선 위값을 계승. 틀릴때 그냥 0 import sys input = sys.stdin.readline str1, str2 = (input().rstrip() for _ in range(2)) n, m = len(str1), len(str2) dp = [[0]*(m+1) for _ in range(n+1)] max_v = 0 for i in ..

말 그대로 귀찮은 문제. 하지만 많이 보던 파일 합치기의 idea가 일부 사용된 문제기도 하다. 가장 작은 부분부터 해결하는게 최소 비용을 보장한다. import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) arr.sort() total = sum(arr) answer = 0 for num in arr: answer += num * (total - num) total -= num print(answer)

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 참 묘한게 처음풀때는 이게 골드4인가 싶었는데 이제는 쉽다. 디버깅 몇 번하고 통과. 전에 푼것보다 훨씬 빠른 코드다. import sys input = sys.stdin.readline from collections import deque def eat_fish(fish, s, c): fish.sort() x, y = fish[0] aquarium[x][y] = 0 c += 1 if c=..