Twinparadox Factory

시간 제한 : 1초 메모리 제한 : 128MB 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 다음 줄부터 T개의 줄에는 헤일스톤 수열의 시작값 n이 주어진다. (1 ≤ n ≤ 100,000) 출력 각각의 테스트 케이스에 대해서, n으로 시작하는 헤일스톤 수열에서 가장 큰 값을 출력한다. 소스코드 #include #include using namespace std; int main(void) { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int T; cin >> T; while (T--) { int n, heils, max; cin >> n; heils = max = n; while (heils!=1) { ..

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

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

모든 쌍의 최단 경로를 구하는 방법을 찾고 싶다면, 다익스트라(Dijkstra) 알고리즘을 모든 정점(Vertex)에 대한 최단경로를 구하거나 다익스트라가 제한되는 경우(음의 가중치가 존재하는 경우)에는 벨만-포드(Bellman-Ford) 알고리즘을 모든 정점(Vertex)에 대해서 사용하면 된다. 플로이드-워셜(Floyd-Warshall) 알고리즘은 앞서 말한 두 알고리즘과는 다르게 처음부터 모든 정점 사이의 최단 경로를 구하는 알고리즘이다. 위 그림은 i에서 j로 가는 방법을 표현한 것으로, k를 경유하는 경우와 그렇지 않은 경우에 대한 것이다. 위 문자의 의미는 1부터 k까지만 경유할 수 있는 상황에서 i에서 j까지 갈 수 있는 모든 경로 중, 가장 짧은 경로의 거리로, 동적계획법(Dynamic P..