Hanbit the Developer

https://www.acmicpc.net/problem/14289 14289번: 본대 산책 3 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net import sys input = sys.stdin.readline MOD = 1000000007 def multiply_matrix(matrix1, matrix2): return [[sum(matrix1[i][k]*matrix2[k][j] % MOD for k in range(n)) % MOD for j in range(n)] for i in range(n)] def solution(D): # DP 초기화 dp1 = [[0]*n for _ in range(n)] for k, v in graph.items():..

https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 먼저 인접행렬을 통해 탐색의 경우의 수를 구하는 방법을 알아보자. 다음과 같은 행렬이 있다고 하자. 이것을 제곱하면 아래처럼 된다. 이것에 이동경로라는 의미를 붙여서 사용한다. 즉, AAAB + ABBB는 (A->A->B의 경우의 수) + (A->B->B의 경우의 수)가 되는 것이다. 또한 행렬2는 총 2번 이동했을 때의 경우의 수를 나타낸다. 여기서, 행렬2와 행렬1을 곱하면 3번 이동했을 때의 경우의 수가 나타난다. 그리고 행렬2를 제곱하면 4번 이동했을 때의 경우의 수가 도출된다. 즉, 행렬1을 N제곱하면 ..

https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net import sys input = sys.stdin.readline def f(n): count = 0 k = 0 while 2**k

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net import java.util.Scanner; import java.util.ArrayList; import java.util.Arrays; public class Main { private static int bisectLeft(ArrayList nums, int value) { int left = 0; int right = nums.size()-1; int mid; while(left= value) ..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net Union-find를 이용한 Kruskal 알고리즘(https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-1197%EB%B2%88-%EC%B5%9C%EC%86%8C-%EC%8A%A4%ED%8C%A8%EB%8B%9D-%ED%8A%B8%EB%A6%AC)을 알고 있다는 가정 하에 작성하였다. 이 문제는 유니온 파인드를 ..

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net #include #include #define CASE 4 #define MIN(a, b) (a= SIZE) return 0; // 한 발판에 두 발을 두는 것 허용X -> DP에 초기에 매우 큰 값이 들어가므로 이것을 리턴한다. // 이렇게 하면, 이것의 상위 함수에서 min을 통해 걸러낼 수 있다. else if (left != 0 && left == righ..

https://www.acmicpc.net/problem/13925 13925번: 수열과 쿼리 13 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) 2 x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y www.acmicpc.net 이 글은 Segment Tree의 Lazy Propagation을 알고 있다는 가정 하에 작성하였다. 자세한 사항은 아래 링크를 참고하자. https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10999%EB%B2%88-%EA%B5%AC%EA%B0%8..

https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net import sys input = sys.stdin.readline def ccw(x1, y1, x2, y2, x3, y3): return (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) def is_two_lines_intersecting(line1, line2): x1, y1, x2, y2 = line1 x3, y3, x4, y4 = line2 m..

https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net import sys input = sys.stdin.readline if __name__ == '__main__': T = int(input()) n = int(input()) A = list(map(int, input().split())) m = int(input()) B = list(map(int, input()...

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net import sys input = sys.stdin.readline def dfs(puttables, index, count): # Base case if index == len(puttables): global max_count max_count = max(max_count, count) return # Recursive case x, y = puttables[index] nx, ny = new_posi..