Twinparadox Factory

시간 제한 : 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

시간 제한 : 1초메모리 제한 : 128MB 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 출력각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다. 소스코드 #include #include using namespace std; int max(int a, int b) { return a < b ? b : a; } int main(void) { int t, n, ans; c..

시간 제한 : 2초메모리 제한 : 128MB 입력첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y). 출력K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 32bit-int 범위를 초과하지 않는다. 소스코드 #include #include using namespace std; int main(void) { vector arr; vector dp; int n, m, t, x1, y..

시간 제한 : 1초메모리 제한 : 128MB 입력첫째 줄에는 할머니가 넘어온 날 D (3≤D≤30)와 그 날 호랑이에게 준 떡의 개수 K (10≤K≤100,000)가 하나의 빈칸을 사이에 두고 주어진다. 출력첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤A≤B)가 존재한다. 소스코드 #include using namespace std; int main(void) { int first[31] = { 0, 1, 0, }, second[30] = { 0, 0, 1, }; int day, rc; int d1=1, d2=1; int i, j; cin >> day >> rc; for (i =..

시간 제한 : 1초메모리 제한 : 256MB 입력첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다. 출력첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최소값을 출력한다. 정답은 2^31-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 2^31-1보다 작거나 같다. 소스코드 #include #include using namespace std; int dp(int arr[], int size) { int** table; int i, j, k, L, tmp, result; table = new int*[size..

시간 제한 : 2초메모리 제한 : 512MB 입력첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000) 출력첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. 소스코드 #include #include using namespace std; int main(void) { pair arr[16] = { {0,0}, }; int dp[16] = { 0, }, n; cin >> n; for (int i = 0; i > arr[i].first >> arr[i].second; for (int i = 0; i < n; i++) { if ..

문서 편집 시 삽입, 삭제, 대체 연산이 사용되며이 때 어떤 특정 문자열 S를 다른 문자열 S`으로 변환시키 과정에서 필요한최소 편집 연산 횟수를 편집 거리(Edit Distance)라고 한다. stable이라는 문자열을 strike로 바꾼다고 할 때를 생각해보자.여러 가지 방법이 존재한다. 첫 번째 방법은 s, t, e는 그대로 두고 ‘abl’을 삭제하고 ‘rik’를 삽입하는 방식으로,3회의 삭제 연산과 3회의 삽입 연산으로 총 6회의 편집 연산이 실행되었다. 두 번째 방법은, s, t, e를 그대로 사용하고 ‘abl’을 ‘rik’로 바꾸기만 하면 stable을 strike로 바꿀 수 있고,3번의 대체가 발생했기 때문에 이 때 총 3회의 편집 연산 실행되었다. 두 문자열을 바꾸는 데 필요한 편집 거리를..

연속된 행렬들의 곱셈에 필요한 원소 간 최소 곱셈 횟수를 찾는 문제로,일단 연속된 행렬 간의 곱셈이 모두 가능하다는 전제 조건 하에 이루어진다. 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)문제라고 한다.그러나, 일반적인 배낭 문제에서는 물건을 쪼개서 담을 수 없어서 다른 방식을 고려해야 한다. 이 때..