Study hard

www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net [풀이] LCS가 여러가지인 경우에 아무거나 출력하라고 했으므로 가장 긴 LCS를 출력하도록 했다. LCS를 구하는 것은 아래 풀이처럼 하고 string LCS[n][m]를 이용하여 첫번째 문자열의 n번째 문자까지와 두번째 문자열의 m번째 문자까지의 최장 LCS를 저장하도록 했다. 2021/02/24 - [백준/DP] - (c++)백준 9251번: LCS (c++..

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net [풀이] dp[i][j] = A문자열의 i번째까지, B문자열의 j번째까지 가장 긴 부분 수열의 길이 #include #include //max #include using namespace std; string A, B; int dp[1001][1001]; void DP() { int N = A.size(); int M = B.size(); for (int i = 1;..

www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net [풀이] bfs를 사용하여 USADO가 k이상인 비디오의 개수를 세 주었다. ※query마다 visited배열을 false로 초기화해야한다. #include #include #include using namespace std; struct Video { int v; int USADO; }; int N, Q; int p, q, r; vectorMoo[5001];..

www.acmicpc.net/problem/2163 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿� www.acmicpc.net [풀이] DP로 풀 수 있다. 먼저 세로로 N번 자르고 각각 조각마다 M번씩 자른다. 점화식 DP[i] = DP[i-1] + N #include using namespace std; int N, M; int DP[301]; void solution() { DP[0] = N - 1;//처음에 세로로 N-1번 자름 for (int i = 1; i < M; i++) DP[i] = DP[i - 1] + N;//..

www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있� www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[x][y]: x번째 소형 기관차가 y번째 객차를 끌고갈 경우 x번째 기관차가 y번째 객차를 끌고가는 경우와 끌고가지 않는 경우를 비교해 줘야 한다. train[]에 해당 인덱스까지의 누적 인원수를 저장한다. res = max(solution(x,y+1), train[y + M - 1] - train[y - 1] + solution(x+1,y+M)) #inclu..

www.acmicpc.net/problem/2281 2281번: 데스노트 첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m� www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[name][len] : 현재 쓰려는 이름의 인덱스, 해당 줄에 지금까지 쓰인 글자 수 다음 줄로 넘어가는 경우와 넘어가지 않고 그 줄에 쓰는 경우를 비교한다. #include #include //memset #include //min using namespace std; int n, m; int Name[1001]; int dp[10..