Twinparadox Factory

시간제한 : 2초메모리 제한 : 128MB 입력첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 소스코드#include #include using namespace std; int main(void) { int N, K, mod = 1000000000; cin >> N >> K; vector dp(201, vector(201, 0)); for (int i = 0; i

시간 제한 : 2초메모리 제한 : 128MB 입력첫째 줄에 3개의 정수 N, P, Q가 주어진다. 출력첫째 줄에 A_N을 출력한다. 소스코드#include #include using namespace std; map dp; long long recursive(long long N, long long& P, long long& Q) { if (N == 0) return 1; else if (dp[N]) return dp[N]; return dp[N] = recursive(N / P, P, Q) + recursive(N / Q, P, Q); } int main(void) { long long N, P, Q; cin >> N >> P >> Q; cout

시간 제한 : 5초메모리 제한 : 512MB 입력첫째 줄에 n (0 ≤ n ≤ 35)이 주어진다. 출력첫째 줄에 t(n)을 출력한다. 소스코드#include using namespace std; int main() { long long dp[36] = { 1, }; int n; cin >> n; for (int i = 1; i

시간 제한 : 2초메모리 제한 : 128MB 입력첫 번째 줄에 자연수 N이 주어진다.(N≤1,000,000) 출력첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다. 소스코드 #include using namespace std; long long dp[1000001] = { 1, 1, }; int main() { int n; cin >> n; for (int i = 2; i

시간 제한 : 1초메모리 제한 : 256MB 입력첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000) 둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다. 출력첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다. 소스코드 #include using namespace std; int arr[1001][1001], dp[1001][1001] = { 0, }; int main(void) { int n, m, max; cin >> n >> m; for (int i = 1; i arr[i][j]; for (int i = 1; i

시간 제한 : 1초메모리 제한 : 256MB 문제2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 소스코드 #include using namespace std; int main(void) { int n, arr[1001] = { 0,1,3 }; cin >> n; for (int i = 3; i

연속된 행렬들의 곱셈에 필요한 원소 간 최소 곱셈 횟수를 찾는 문제로,일단 연속된 행렬 간의 곱셈이 모두 가능하다는 전제 조건 하에 이루어진다. A=10X20, B=20X5, C=5X15 다음 세 행렬에 대한 계산을 예로 들면, AxBxC는 두 가지 방법으로 계산할 수 있다. 1. (AxB)xC2. Ax(BxC) 두 가지 계산은 결과는 아무 차이가 없지만, 순서에 따라서 두 행렬 곱셈의 횟수가 차이가 나기 때문에이를 최소화하고자 하는 방법을 구성할 필요가 있다. 일단, 1번의 계산을 예로 들면, 1번의 계산에서는 AxB는 10x20x5로, 1000회의 원소 곱셈을 시행하고,AxB 행렬은 10x5로, (AxB)xC는 750회 곱셈을 진행해 전체적으로 1750회의 원소 곱셈을 시행해야 한다. 2번의 계산은 ..

Algorithm] Knapsack(배낭 문제) - 동적계획법 처음 내가 알고리즘 문제를 접했을 때 처음으로 배낭 문제를 접근했던 방식은 그리디였다.그리디는 다들 알고 있듯, 선택에 대한 번복도 없고, 근시안적인 선택으로 인해서경우에 따라서는 최적해를 보장하지 못하는 문제가 발생한다. 모든 배낭 문제에 대해서 그리디가 유효한 방법이 될 수 없는 건 아니고,물건을 임의로 쪼개어 담을 수 있는(용량을 정할 수 있는) 배낭 문제라면,무게 당 가격을 계산해서 적당히 담는 걸 고려하여 최적해를 구할 수 있기 때문에그리디 알고리즘으로는 해결이 가능하며 이를 부분 배낭(Fractional Knapsack)문제라고 한다.그러나, 일반적인 배낭 문제에서는 물건을 쪼개서 담을 수 없어서 다른 방식을 고려해야 한다. 이 때..