HTD

def gcd(x, y): if y != 0: return gcd(y, x % y) else: return x def lcm(x, y): return (x*y)//gcd(x, y)

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 일반화에 실패하여 이 문제의 특징을 파악하고자 시간복잡도를 통과하지 못하지만 정확성이 있는 코드를 작성하였다. 0이 8개, 1이 5개가 있을 때의 경우의 수는 무엇일까? 이를 중복조합을 통해 구할 수 있다. 위 사진의 경우에는 5개의 1이 5개의 공간들 중 1개씩 고르면 되므로, c0, c1이 각각 0, 1의 갯수(각각 8, 5)라고 했을 때, 다음의 식으로 구할 수 있다. 이것을 기반으로 코드를 작성..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net import sys input = sys.stdin.readline MAX = 101 def w(a, b, c): if dp[a][b][c] == -1: if a 20: dp[a][b][c] = w(20, 20, 20) elif a < b and b < c: dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) else: dp[a][b][c] = w..

https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net import sys import math input = sys.stdin.readline sys.setrecursionlimit(1000000) def get_tree_length(N): if N & (N-1) == 0: return 2*N else: return pow(2, math.ceil(math.log(N, 2)) + 1) def i..

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