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

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

시간 제한 : 2초메모리 제한 : 128MB 입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. 출력첫째 줄에 연산을 하는 횟수의 최소값을 출력한다. 소스코드 #include #define MIN(a,b) ((a) n; cout

시간 제한 : 1초메모리 제한 : 256MB 입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다. 소스코드 #include using namespace std; int main(void) { int max, n, arr[1001] = { 0, }, dp[1001] = { 0, }; cin >> n; for (int i = 1; i > arr[i]; dp[i] = arr[i]; } 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

시간 제한 : 2초메모리 제한 : 128MB 문제N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력첫째 줄에 구한 0의 개수를 출력한다. 소스코드 #include using namespace std; int main(void) { int dp[501], n; cin >> n; for (int i = 0; i

시간 제한 : 2 초메모리 제한 : 128 MB 문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도..

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

문서 편집 시 삽입, 삭제, 대체 연산이 사용되며이 때 어떤 특정 문자열 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번의 계산은 ..