'Problem Solve/Dynamic Programming' 카테고리의 글 목록

[백준] 9251번 LSC (C)

문제 주소 백준 9251번 LSC 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 알고리즘 DP 힌트 첫번째 문자열의 i번 문자까지의 문자열과 두번째 문자열의 j번 문자까지의 문자열의 LCS의 길이를 구한다. 문제풀이 dp[i][j]에 문자열 a의 i번 문자까지의 문자열과 문자열 b의 j번 문자까지의 문자열의 LCS의 길이를 저장한다. 가장 끝의 문자만 비교하는 식으로 길이를 구해나갈 수 있다. 끝 문자가 같을 경우 dp[i][j] = dp[i-1][j-1]+1 끝..

Problem Solve/Dynamic Programming 2020. 4. 21. 09:49

[백준] 2565번 전깃줄 (C)

문제 출처 한국정보올림피아드 지역본선 2007 초등부 4번 문제 주소 백준 2565번 전깃줄 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net 알고리즘 DP 힌트 서로 교차하지 않는 전깃줄의 최대 개수를 구한다. 문제풀이 서로 교차하지 않는 전깃줄의 최대 개수를 구하기 위해선 한 쪽 전봇대 기준으로 정렬을 한 뒤 나머지 전봇대의 번호에서 가장 긴 증가하는 수열을 구하면 된다. #include ..

Problem Solve/Dynamic Programming 2020. 4. 12. 00:31

[백준] 11054번 가장 긴 바이토닉 부분 수열 (C)

문제 주소 백준 11054번 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 알고리즘 DP 힌트 i위치까지 가장 긴 증가하는 부분수열의 길이와 i위치까지 가장 긴 감소하는 부분 수열의 길이를 구한다. 문제풀이 dp[i][0]에 i위치까지 가장 긴 증가하는 부분수열의 길이 dp[i][1]에 i위치까지 가장 긴 감소하는 부분 수열의 길이를 저장하고 두 합이 가장 큰 것의 값을 구한다. #include using namespace std; int in[1002]; int dp[1002][2]; int mai..

Problem Solve/Dynamic Programming 2020. 4. 9. 12:59

[백준] 11053번 가장 긴 증가하는 부분 수열 (C)

문제 주소 백준 11053번 가장 긴 증가하는 부분 수열 불러오는 중입니다... 알고리즘 DP 힌트 dp배열에 i번째 수 까지 가장 긴 증가하는 부분 수열의 길이를 저장한다. 문제풀이 i번째 수 까지 가장 긴 증가하는 부분 수열의 길이를 구하기 위해선 i번째 이하의 1~i-1의 구간의 수를 j라 할 때 in[i]가 in[j]보다 크다면 dp[j]+1, 작다면 dp[j]를 선택한 값의 최대값을 구하면 된다. 답은 dp[1]~dp[n]까지의 수 중 최대값이다. #include using namespace std; int dp[1001]; int in[1001]; int main(){ int n; cin>>n; for(int i=1;i>in[i]; int ans=0; for(int i=1;i

Problem Solve/Dynamic Programming 2020. 4. 6. 11:41

[백준] 2156번 포도주 시식 (C)

문제 주소 백준 2156번 포도주 시식 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 알고리즘 DP 힌트 dp배열에 그날 포도주를 마셨을 때와 마시지 않았을 때의 최대값을 저장한다. 문제풀이 dp[i][0], dp[i][1]은 각각 i번째까지의 ..

Problem Solve/Dynamic Programming 2020. 3. 30. 18:40

[백준] 10844번 쉬운 계산 수 (C)

문제 주소 백준 10844번 쉬운 계산 수 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 DP 힌트 dp배열에 i자리수중 j로 끝나는 수의 개수를 저장한다. 문제풀이 dp배열에 i자리 수중 j로 끝나는 수의 개수를 dp[i][j]에 저장한다. 0으로 끝나는 경우와 9로 끝나는 경우 그 이전의 수가 될 수 있는 수는 1과 8밖에 없기 때문에 따로 처리해준다. #include using namespace std; int dp[101][10]; int main(){ int n; cin>>n; //초기항 설정 for(int i=1;i

Problem Solve/Dynamic Programming 2020. 3. 30. 00:15

[백준] 1932번 정수 삼각형 (C)

#include using namespace std; int in[501][501]; int dp[501][501]; int main(){ int n; cin>>n; int ans=0; for(int i=1;iin[i][j]; dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+in[i][j]; ans=max(ans,dp[i][j]); } } cout

Problem Solve/Dynamic Programming 2020. 3. 29. 23:53

[백준] 1149번 RGB거리

문제 주소 백준 1149번 RGB거리 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 DP 힌트 배열에 각 집에서 각각의 색을 칠하는데 최소 비용을 저장한다. 문제 풀이 dp배열은 그 집에서 각 색을 칠할때의 최소 비용을 저장하는 배열이다. RGB를 각각 012원소에 넣고 i번째 집에서 0번째 색을 칠하기 위한 최소 비용은 i-1번째 집에서 1 또는 2를 칠하기 위한 최소 비용중 작은 값에 cost[i][0]을 더한 값이다. #include using names..

Problem Solve/Dynamic Programming 2020. 3. 28. 22:39

[백준] 9461번 파도반 수열 (C)

문제 출처 ICPC Asia Pacific Korea Asia Regional - Daejeon 2013 G번 문제 주소 백준 9461번 파도반 수열 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하 www.acmicpc.net 알고리즘 DP 힌트 n번째 삼각형 변의 길이와 이..

Problem Solve/Dynamic Programming 2020. 3. 28. 22:24

[백준] 1904번 01타일 (C)

#include using namespace std; int dp[1000001]; int main(){ int n; cin>>n; dp[1]=1; dp[2]=2; for(int i=3;i

Problem Solve/Dynamic Programming 2020. 3. 28. 22:12

낭만 IT

Problem Solve/Dynamic Programming → (12)건