반응형
https://www.acmicpc.net/problem/1010

조합

동적계획법


문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)


재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.



code>> 


#include<iostream>

#include <string.h>

int memo[31][31];

long Solve(const int& n, const int& r)

{

if (n == r || r == 0)

return 1;

if (memo[n][r] != -1)

return memo[n][r];

return memo[n][r] = Solve(n - 1, r - 1) + Solve(n - 1, r);

}

int main()

{

std::ios::ios_base::sync_with_stdio(false);

int T, N, M;

std::cin >> T;

while (T-- > 0)

{

std::cin >> N >> M;

memset(memo, -1, sizeof(memo));

printf("%ld\n", Solve(M, N));

}

return 0;

}



반응형
저작자표시 비영리

'알고리즘 > 백준' 카테고리의 다른 글

1766>문제집  (0) 2019.03.12
1654>랜선 자르기  (0) 2019.02.18
11657>타임머신  (0) 2018.12.04
1786>찾기  (0) 2018.11.26
11062>카드 게임  (0) 2018.11.19
반응형

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.


예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.


입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.


code>>


#include <iostream>

#include <string>

#include <algorithm>

#include <stack>

int memo[1001][1001] = { 0 };

int main()

{

std::ios::ios_base::sync_with_stdio(false);

std::string input1, input2;;

std::cin >> input1 >> input2;

input1 = input1.insert(0, "0");

input2 = input2.insert(0, "0");

for (int i = 1; i < input1.size(); i++)

{

for (auto ii = 1; ii < input2.size(); ii++)

{

if (input1[i] == input2[ii])

memo[i][ii] = memo[i - 1][ii - 1] + 1;

else

memo[i][ii] = std::max(memo[i][ii - 1], memo[i - 1][ii]);

}

}

std::stack<char> stack;

int i = input1.size()-1;

int ii = input2.size()-1;

while (ii > 0 && i > 0)

{

if (input1[i] == input2[ii])

{

stack.push(input2[ii]);

ii--; i--;

}

else

{

if (memo[i - 1][ii] > memo[i][ii-1])

i--;

else

ii--;

}

}

printf("%d\n",stack.size());

while(!stack.empty())

{

printf("%c", stack.top());

stack.pop();

}

printf("\n");

return 0;

}

반응형
저작자표시 비영리

'알고리즘 > 백준' 카테고리의 다른 글

1005>ACM Craft  (0) 2018.09.20
2231>분해합  (0) 2018.09.02
9251>LCS  (0) 2018.08.04
1920>수 찾기  (0) 2018.06.24
1780>종이의 개수  (0) 2018.06.22
반응형

https://www.acmicpc.net/problem/1463


동적계획법


문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.


X가 3으로 나누어 떨어지면, 3으로 나눈다.

X가 2로 나누어 떨어지면, 2로 나눈다.

1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.


입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. 


반례 찾기 너무 힘들다..


code>>


#include <iostream>

#include <algorithm>

#include <string.h>

int memo[1000001];

int input;

int Recursion(int val)

{

if (val == 1) return 0;

if (memo[val] != -1) return memo[val];

int ans = memo[val] = input;

if (val % 3 == 0)

ans = std::min(ans, Recursion(val / 3) + 1);

if (val % 2 == 0)

ans = std::min(ans, Recursion(val / 2) + 1);

ans = std::min(ans, Recursion(val - 1) + 1);

if (memo[val] > ans)

memo[val] = ans;

return memo[val];

}

int main()

{

std::ios_base::sync_with_stdio(false);

std::cin >> input;

memset(memo, -1, sizeof(memo));

memo[2] = memo[3] = 1;

printf("%d\n", Recursion(input));

return 0;

}

반응형
저작자표시 비영리

'알고리즘 > 백준' 카테고리의 다른 글

2912>백설공주와 난쟁이  (0) 2018.06.13
7568>덩치  (0) 2018.06.09
6603>로또  (0) 2018.05.28
1504>특정한 최단 경로  (0) 2018.05.27
1753>최단경로  (0) 2018.05.19
반응형

https://www.acmicpc.net/problem/9461


동적계획법


문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.


파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.


N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.


입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)


code>>


오랜만에 배열 규칙 발견한 듯..


#include<stdio.h>

#include<string.h>

long long memo[101];

int main()

{

memset(memo, -1, sizeof(memo));

long long temp[8] = {1, 1, 1, 2, 2, 3, 4, 5 };

memcpy(memo, temp, sizeof(temp));

for (int i = 8; i < 100; i++)

{

memo[i] = memo[i - 1] + memo[i - 5];

}

int t = 1;

scanf("%d", &t);

int input;

for (int i = 0; i < t; i++)

{

scanf("%d", &input);

printf("%lld\n", memo[input - 1]);

}

    return 0;

}

반응형
저작자표시 비영리

'알고리즘 > 백준' 카테고리의 다른 글

1934, 13241>최소공배수  (0) 2018.03.24
1057>토너먼트  (0) 2018.03.24
1912>연속합  (0) 2018.03.17
7569>토마토  (0) 2018.03.10
7576>토마토  (0) 2018.03.10
반응형

https://www.acmicpc.net/problem/1912


동적계획법


문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다.


예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.


입력

첫째 줄에 정수 n(1≤n≤100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.


code >>


#include<stdio.h>

#include<algorithm>

#include<string.h>

int input[100001] = {10, -4, 3, 1, 5, 6, -35, 12, 21, -1};

int memo[100002];

int size = 11;

int GetSolve(int index)

{

if (index >= size) return -987654321;

if (memo[index] != -987654321) return memo[index];

memo[index] = std::max(GetSolve(index + 1) + input[index], input[index]);

return memo[index];

}

int main()

{

scanf("%d", &size);

for (int i = 0; i < size; i++)

{

scanf("%d", &input[i]);

memo[i] = -987654321;

}

GetSolve(0);

int max = -987654321;

for (int i = 0; i < size; i++)

{

if (max < memo[i]) max = memo[i];

}

printf("%d", max);

    return 0;

}

반응형
저작자표시 비영리

'알고리즘 > 백준' 카테고리의 다른 글

1057>토너먼트  (0) 2018.03.24
9461>파도반 수열  (2) 2018.03.17
7569>토마토  (0) 2018.03.10
7576>토마토  (0) 2018.03.10
1520>내리막길  (0) 2018.03.10
반응형

https://www.acmicpc.net/problem/1520


동적계획법 + DFS


문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.



현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.





지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.


입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.



남들보다 소스코드가 긴데.. 다음 값을 확인하는 함수를 따로 빼놔서 그렇다.


code >>


#include<stdio.h>

#include <string.h>

#define MAX 500

int mx[4] = { 0, 0, -1, 1 };//상하좌우

int my[4] = { -1, 1, 0, 0 };//상하좌우

int memo[MAX + 1][MAX + 1];

int maze[MAX][MAX];

int max_x = 5;

int max_y = 4;


bool Next(int x, int y, int idx)

{

if (x + mx[idx] >= 0 && x + mx[idx] < max_x && y + my[idx] >= 0 && y + my[idx] < max_y)

return true;

else 

return false;

}

int DFS(int x, int y)

{

if (x == max_x - 1 && y == max_y - 1) return 1;

if (x < 0 || x >= max_x || y < 0 || y >= max_y) return 0;

if (memo[y][x] != -1) 

return memo[y][x];


memo[y][x] = 0;

for (int i = 0; i < 4; i++)

{

if (Next(x, y, i) && maze[y][x] > maze[y + my[i]][x + mx[i]])

{

memo[y][x] += DFS(x + mx[i], y + my[i]);

}

}

return memo[y][x];

}

int main()

{

scanf("%d %d", &max_y, &max_x);

for (int y = 0; y < max_y; y++)

{

for (int x = 0; x < max_x; x++)

{

scanf("%d", &maze[y][x]);

}

}

memset(&memo, -1, sizeof(memo));

printf("%d\n", DFS(0, 0));

    return 0;

}



반응형
저작자표시 비영리

'알고리즘 > 백준' 카테고리의 다른 글

7569>토마토  (0) 2018.03.10
7576>토마토  (0) 2018.03.10
2156>포도주 시식  (0) 2018.02.26
1932>숫자 삼각형  (0) 2018.02.15
1094>막대기  (0) 2018.02.04
반응형
https://www.acmicpc.net/problem/2156

동적계획법


문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.


포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.

연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 


예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.


입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.



testcase >


8 7 7 0 5 7 7 0 3

7 7 0 5 7 7 0 3

6 6 10 13 9 8 1


code>>


#include<stdio.h>

#include<string.h>

#include<algorithm>


int list[10000] = { 10, 22, 1 ,10,  };

int max = 4;

int memo[10001][3];


int Solve(int idx, int select)

{

if (idx >= max) return 0;

if (memo[idx][select] != -1) return memo[idx][select];

int temp = Solve(idx + 1, 0);

if (select < 2)

temp = std::max(temp, Solve(idx + 1, select + 1) + list[idx]);

else

temp = std::max(temp, Solve(idx + 2, 0));

return memo[idx][select] = temp;

}

int main()

{

scanf("%d", &max);

for (int i = 0; i < max; i++)

scanf("%d", &list[i]);

memset(memo, -1, sizeof(memo));

printf("%d\n", Solve(0, 0));

    return 0;

}



반응형
저작자표시 비영리

'알고리즘 > 백준' 카테고리의 다른 글

7576>토마토  (0) 2018.03.10
1520>내리막길  (0) 2018.03.10
1932>숫자 삼각형  (0) 2018.02.15
1094>막대기  (0) 2018.02.04
2455>지능형 기차  (0) 2018.02.04
반응형

https://www.acmicpc.net/problem/2579


동적계획법


 문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.




예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째, 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.



계단 오르는 데는 다음과 같은 규칙이 있다.


계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.

마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세번째 계단을 연속해서 모두 밟을 수는 없다.


각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최대값을 구하는 프로그램을 작성하시오.


입력

입력의 첫째 줄에 계단의 개수가 주어진다.


둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.



1 2 3

1 1 0 0 1 1

3 3 2 2 4 1


code >>


#include<stdio.h>

#include<string.h>

#include<algorithm>

int list[300];

int size;

int dp[301];

int Solve(int idx, int jump)

{

if (idx == 0 ) return list[0];

if (idx == 1)

{

if (jump == 1) return list[1];

else return list[1] + list[0];

}

if (jump == 1)

{

if (dp[idx] > 0) return dp[idx];

return dp[idx] = Solve(idx - 2, 2) + list[idx];

}

else

{

return std::max(Solve(idx - 1, 1), Solve(idx - 2, 2)) + list[idx];

}

}

int main()

{

scanf("%d", &size);

for (int i = 0; i < size; i++) scanf("%d", &list[i]);


memset(&dp, 0, sizeof(dp));

printf("%d\n", Solve(size-1 , 2));

return 0;

}


반응형
저작자표시 비영리

'알고리즘 > 백준' 카테고리의 다른 글

1094>막대기  (0) 2018.02.04
2455>지능형 기차  (0) 2018.02.04
2965>캥거루 세마리  (0) 2018.01.24
2812>크게 만들기  (0) 2017.12.24
10844>쉬운 계단 수  (0) 2017.12.23
반응형

부산에 중견 코딩 테스트 때 나왔던 문제인데 스터디 같이 하시던 분이 부산 가셔서 테스트 보시고 문제 들고 오심.


최대 1000으로 생각한다.


N=4

1+1+1+1

1+1+2

2+2

3+1


#include<stdio.h>

#include<string.h>

#include <chrono>

int N = 4;

long long memo[1001][1001];

using namespace std;

using namespace chrono;

int GetValue(int idx, int sum)

{

if (sum > N)return 0;

if (sum == N) return 1;

if (memo[idx][sum] != -1) return memo[idx][sum];

long long count = 0;

for (int i = idx; i < N; i++)

{

if (sum + i > N) break;

count += GetValue(i, sum + i);

}

return memo[idx][sum] = count;

}

int main()

{

scanf("%d", &N);

long long count = 0;

system_clock::time_point start = system_clock::now();

memset(memo, -1, sizeof(memo));

for(int i=1; i<N;i++)

count += GetValue(i, i);

printf("%lld\n", count);

system_clock::time_point end = system_clock::now();

duration<double> sec = end - start;

printf("%lf", sec);

    return 0;

}

반응형
저작자표시 비영리

'알고리즘 > 기타' 카테고리의 다른 글

기수 정렬(RadixSort) 구현  (0) 2018.03.22
계수 정렬(CountingSort) 구현  (0) 2018.03.20
QuickSort 구현  (0) 2018.03.10
heap 정렬 및 PriorityQueue  (0) 2018.02.10
후위 표기법  (0) 2018.01.04
반응형

https://www.acmicpc.net/problem/10844

동적계획법


문제

45656이란 수를 보자.


이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.


세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.


N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)


입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.


code>>


#include<stdio.h>

#include<string.h>

using namespace std;

int N = 1;

int memo[101][10];

int GetValue(int n, int v)

{

if (n == 1) return v < 0 || v > 9 ? 0 : 1;

if (v < 0 || v > 9) return 0;

if (memo[n][v] != -1)return memo[n][v];

return memo[n][v] = (GetValue(n - 1, v + 1) + GetValue(n - 1, v - 1)) % 1000000000;

}

int main()

{

int count = 0;

memset(memo, -1, sizeof(memo));

scanf("%d", &N);

for (int i = 1; i < 10; i++)

{

count = (count + GetValue(N, i)) % 1000000000;

}

printf("%d\n", count);

    return 0;

}


언젠간 for문 점화식으로 푸는 날이 있겠지

반응형
저작자표시 비영리

'알고리즘 > 백준' 카테고리의 다른 글

2965>캥거루 세마리  (0) 2018.01.24
2812>크게 만들기  (0) 2017.12.24
1065>한수  (0) 2017.12.16
11312>삼각 무늬1, 2  (0) 2017.12.16
1149>RGB 거리  (0) 2017.12.15

+ Recent posts

티스토리툴바