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

시간 제한 : 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초메모리 제한 : 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 ..

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

시간 제한 : 2초메모리 제한 : 128MB 입력입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 > t; for (int i = 0; i

시간 제한 : 1초메모리 제한 : 256MB 입력첫째 줄에 도시의 개수 n(1≤n≤100)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 출력N개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다. 소스코드 #include #define ..

이전 포스팅에서도 말했다시피, 일반적인 재귀 방법을 사용하는 건 시간이 오래 걸린다는 단점을 가지고 있다. 메모화재귀는 동적계획법을 재귀적으로 사용하는 것으로 동적계획법의 일종으로한 번 계산이 진행된 것은 추가로 진행하지 않는 것을 목표로 하기 때문에깊이 우선 탐색을 응용해 (1,1)에 하위에서 생성된 계산값을 미리 작성해두어만일 다시 접근이 이뤄지면 그 값을 반환시키는 것을 말한다. 깊이 우선 탐색을 통해서 일반적인 재귀 방법으로 접근했을 때 중복되는 작업들을 많이 걸러낼 수 있어서제한 시간 초과라는 문제를 극복할 수 있다. const int h = 5, w = 4; int Memo_recursion[h + 1][w + 1]; int dfs(int nowh, int noww) { if (nowh > h..