작심 24/7

11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 � www.acmicpc.net 근우 입장에서 볼 때 근우 차례 : 점수가 더 높은 카드를 갖고 감으로써 점수를 최대로 하는 플레이를 해야 함 명우 차례 : 명우 입장에선 자신이 이기기 위해 점수가 더 높은 카드를 갖고 갈 것이므로 근우는 근우의 점수를 최소로 하는 플레이를 해야 함 DP[i][j] = i번째부터 j번째 카드가 있을 때 근우가 얻을 수 있는 최대 점수 근우 차례일 땐 점수를 최대로 해야 하므로 max(왼쪽 카드 + 왼쪽 카드를 뽑고 플레이한 결과, 오른쪽 카드 + 오른쪽 카드를 ..

16890번: 창업 입력은 길이가 N(1 ≤ N ≤ 300,000)인 문자열 두 개로 이루어져 있다. 모든 문자열은 알파벳 소문자로만 이루어져 있다. 첫 번째 줄에 주어지는 문자열은 구사과가 고른 문자이고, 두 번째 줄에 주�� www.acmicpc.net 구사과는 사전 순으로 가장 앞서게 만들고 싶어 하므로 오름차순 정렬한다. 큐브러버는 사전 순으로 가장 뒤에 오게 만들고 싶어 하므로 내림차순 정렬한다. 회사의 이름은 N개의 문자열로 이루어져 있고 고르는 순서는 항상 구사과가 먼저이므로 구사과 문자열에서 (N+1)/2개, 큐브러버 문자열에서 N/2개 를 골라야 한다. ex) koooosaga → aagkoooos cubelover → vuroleecb 1번째 - 구사과 차례 aagko 에서 제일 작은 ..

1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 수학적으로 풀어도 되지만 백트래킹으로 풀어보았다. 계산에 사용되는 M개의 알파벳을 모아놓고 9부터 M개의 숫자를 순열로 대입하였다. ex) ADC -> 3개의 숫자 9, 8, 7을 순열로 배치시키면 알파벳 ADC는 987, 978, 897, 879, 798, 789 이렇게 숫자가 대입될 수 있다. map을 이용해서 각 알파벳에 숫자를 대입해주고 배치가 완료되면 단어의 합을 계산해주고 최댓값을 갱신한다. 이때 stoi를 이용하여 계산을 했었는데 시간 초과 나..

16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 �� www.acmicpc.net 문자열 S를 처음부터 탐색하면서 현재 idx부터 목록 A에 있는 단어가 포함돼 있으면 재귀 호출로 (idx+단어 길이)번째부터 목록 A에 있는 단어가 있는지 탐색한다. 이때 dp[idx]가 true면 이전에 이 idx부터 시작되는 단어를 탐색해봤다는 뜻이므로 굳이 또 계산할 필요 없이 return으로 돌아온다. dp[idx]가 false면 처음 탐색한다는 뜻이므로 true로 바꿔주고 탐색하러 간다. idx와 문자열 S의 길이가 같다면 성..

11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net map을 이용하여 숫자 카드의 개수를 세고 copy 함수를 이용해 map을 vector에 복사해준 뒤 카드의 개수를 기준으로 내림차순, 카드 숫자를 기준으로 오름차순 정렬한 결과 맨 첫 번째 값을 출력해준다. #include #include #include #include #include using namespace std; int N; long long a; map m; vector v; bool compare(pair a, pair b) ..

9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS(Longest Common Subsequence) 문제이다. LCS(Longest Common Substring)과 같이 문자열 A, B에서 A[i]와 B[j]가 같을 때는 DP[i][j] = DP[i-1][j-1] + 1 이 되지만 A[i]와 B[j]가 다를 때는 DP[i][j] = max(DP[i-1][j], DP[i][j-1]) + 1 이 된다. 그러면 최종적으로 DP[문자열A 끝][문자열B 끝]이 L..

5582번: 공통 부분 문자열 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예 www.acmicpc.net LCS(Longest Common Substring) 문제이다. 문자열 A, B에서 A[i]와 B[j]가 같을 때, DP[i][j] = DP[i-1][j-1] + 1 이 된다. 무슨 말이냐 하면 문자열 A는 ABCDE이고 B는 CDEGG라 할 때 예를 들어 A[4]과 B[2]가 E로 같으면 그 전까지의 문자열 ABCD와 CD에서 가장 길었던 문자열의 길이(DP[3][1])에 E 길이 1을 더한 값이 DP[4][2]에 들어가게 된다. DP 배열의 값 중..

7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활�� www.acmicpc.net 처음엔 1부터 M까지 메모리를 기준으로 비용을 구하려 했는데 시간 초과가 눈에 뻔해서 다른 방법으로 바꾸었다. 0부터 최댓값(모든 비용을 다 더한 값)까지 비용을 기준으로 배낭 채우기 방식을 이용하여 최대 메모리를 dp배열에 채워 넣는다. 최종 배열에서 가장 먼저 M이상인 값이 나온 인덱스를 출력하면 그게 바로 최소 비용이다. #include #include using namespace std; int N, M, cnt, mem[101], cost[101], dp[..