Hanbit the Developer

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

https://www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net import sys import math input = sys.stdin.readline def getTreeLength(): # 2의 제곱꼴인지 확인 if N & (N - 1) == 0: return 2*N - 1 else: return pow(2, math.ceil(math.log(N, 2)) + 1) - 1 def initializeSegmentT..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net import sys input = sys.stdin.readline def initializeSegmentTree(index, start, end): if start == end: tree[index] = (nums[start], nums[start]) return mid = (start + end)//2 initializeSegmentTree(index*2,..

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net import sys input = sys.stdin.readline DIV = 1000000007 def initializeSegmentTree(index, start, end): if start == end: tree[index] = nums[start] else: mid = (start + end)//2 tree[index] = i..

https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net import sys input = sys.stdin.readline def solution(): ccw123 = ccw(x1, y1, x2, y2, x3, y3) ccw124 = ccw(x1, y1, x2, y2, x4, y4) ccw341 = ccw(x3, y3, x4, y4, x1, y1) ccw342 = ccw(x3, y3, x4, y4, x2, y2) # 평행 if ccw123*ccw124 == 0 and ccw341*ccw342 == 0: if mx1