HTD

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

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net import sys input = sys.stdin.readline def getPossiblePathCount(): possiblePathCount = 0 # 가로 for i in range(N): isValidPath = True isRunwayPut = [False]*N for j in range(N-1): c, n = heights[i][j], heights[i][j+1] # 같을 경우 if c == n: con..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net import sys sys.setrecursionlimit(200000) input = sys.stdin.readline dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def dfs(x, y): # 이미 방문한 적이 있을 경우 if dp[x][y] != -1: return dp[x][y] # Base case if x == M-1 and y == N-1: return 1 # Rec..

https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net import sys sys.setrecursionlimit(200000) input = sys.stdin.readline NOT_INITIALIZED, TRUE, FALSE = 0, 1, 2 def getMinCount(): todo = [0] for c in range(input_len+1): nextTodo = [] while..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net import sys import math import itertools input = sys.stdin.readline def getDistance(p1, p2): return math.sqrt(((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)) def find(x): if parent[x] == x: return x px = find(parent[x]) parent[x] ..

https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net import sys import itertools input = sys.stdin.readline def getPointsSum(points): xSum, ySum = 0, 0 for x, y in points: xSum += x ySum += y return xSum, ySum if __name__ == '__main__': T = int(input()) for _ in range(T)..

https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간 (≤ 10,000)이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. www.acmicpc.net import sys input = sys.stdin.readline def getSum(): sum = 0 isAdded = [[False]*N for _ in range(N)] for i in range(N): dp = djikstra(i) # 불가능한 경우 if dp == False: return -1 # dp를 돌면서 sum for j in range(N): dpLe..