Hanbit the Developer

https://www.acmicpc.net/problem/7575 7575번: 바이러스 첫 번째 줄에는 감염된 프로그램의 개수 N 과 바이러스 코드 추정을 위한 최소 길이를 나타내는 정수 K 가 주어진다. 단, 2 ≤ N ≤ 100이고, 4 ≤ K ≤ 1,000이다. 두 번째 줄부터 각 프로그램에 대한 www.acmicpc.net import sys input = sys.stdin.readline def get_pi(keyword): keyword_length = len(keyword) pi = [0]*keyword_length j = 0 for i in range(1, keyword_length): while j > 0 and keyword[i] != keyword[j]: j = pi[j-1] if k..

https://www.acmicpc.net/problem/3356 3356번: 라디오 전송 첫째 줄에 S의 길이 L이 주어진다. 둘째 줄에는 길이가 L인 S가 주어진다. 메시지는 알파벳 소문자로만 이루어져 있다. (1 ≤ L ≤ 1,000,000) www.acmicpc.net import sys input = sys.stdin.readline def get_pi(string): string_length = len(string) pi = [0]*string_length j = 0 for i in range(1, string_length): while j > 0 and string[i] != string[j]: j = pi[j-1] if string[i] == string[j]: j += 1 pi[i] = ..

https://www.acmicpc.net/problem/2533 import sys sys.setrecursionlimit(300000) input = sys.stdin.readline TRUE, FALSE = 1, 0 INF = 1000001 def dfs(is_early_adapter, node, prev): # If dp already exists if dp[is_early_adapter][node] != INF: return adapter_count = is_early_adapter if is_early_adapter == TRUE: for n in graph[node]: if n == prev: continue dfs(TRUE, n, node) dfs(FALSE, n, node) adapter..

https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 먼저, 예시 입력 1의 전깃줄을 정렬하면 다음과 같다. 1 8 2 2 3 9 4 1 6 4 7 6 9 7 10 10 여기서 전깃줄이 안 꼬인다는 것은, 계속해서 값이 커져야만 한다. 즉, 가장 긴 증가하는 부분 수열을 구한다. O(NlogN)으로 가장 긴 증가하는 부분 수열을 구하는 것은 아래 링크에 설명되어있다. https://rccode.tistory.com/entry/14003 [Pyth..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net import sys input = sys.stdin.readline if __name__ == '__main__': N = int(input()) costs = [0]*(N+1) for i in range(1, N+1): cur_input = list(map(int, input().split())) prev_max_time = 0 for j in range(2, 2 + cur_input[..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net import sys input = sys.stdin.readline if __name__ == '__main__': n, m = map(int, input().split()) nums = [[0]*(m+1)] + [[0] + [int(c) for c in str(input().rstrip())] for _ in range(n)] dp = [[0]*(m+1) for _ in range(n+1)] max_length = 0 for i in range(1, n+1): fo..

https://www.acmicpc.net/problem/14722 14722번: 우유 도시 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net import sys sys.setrecursionlimit(100000) input = sys.stdin.readline STRAWBERRY, CHOCOLATE, BANANA = 0, 1, 2 def getMaxMilkCount(toEat, x, y): # Recursive case if x == N-1 and y == N-1: if milks[x][y] == toEat: return 1 else: ..

https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net import sys input = sys.stdin.readline COST1, COST3, COST5 = 10000, 25000, 37000 def dfs(date, coupon): # Base case if date > N: return 0 # Skip the function if dp already exists if dp[date][coupon] != -1: return dp[date][coupon]..

https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 우선 중요한 요소들이 몇 개 있다. 1. L이 1번이라도 들어갔는가 2. 맨 뒤에 A가 1번 붙었는가 3. 맨 뒤에 A가 2번 연속으로 붙었는가 이것을 통해 '상태'를 총 6개를 만들 수 있다. 상태의 네이밍과 설명은 다음과 같다. - O: 기본 - A: 맨 뒤에 A 1개 - AA: 맨 뒤에 A 2개 - L: L이 1개 있고, 맨 뒤에 A 없음 - LA: L이 1개 있고, 맨 뒤에 A 1개 - LAA: L이 ..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net import sys input = sys.stdin.readline def find(x): if parent[x] == x: return x parent[x] = find(parent[x]) return parent[x] def union(x, y): px, py = find(x), find(y) if px < py: parent[py] = px else: p..