푸으름

✏️ 문제 링크https://www.acmicpc.net/problem/2579  ✏️ 문제 설명  ✏️ 문제 풀이가장 먼저 dp배열을 만들어줬는데 dp[i]는 i번째 계단을 밟을 때 얻을 수 있는 최대의 점수로 지정하였습니다. 그리고 나서 dp[1], dp[2], dp[3]값을 각각 지정해 주었습니다. dp[1] = stair[1]이고 dp[2] = stair[1] + stair[2]이고 dp[3]의 경우를 잘 생각해주어야 합니다. 왜냐면 3번째 계단은 1번째 계단 + 3번째 계단 이거나 2번째 계단 + 3번째 계단인 경우 중 하나이기 때문에 다짜고짜 반복문을 돌리게 되면 dp[3]에 다른 값이 지정되지 않을 수도 있습니다. 그런다음 반복문을 돌리면서 dp[i]의 값을 갱신해 주었습니다.dp[i] = ..

✏️ 문제 링크https://www.acmicpc.net/problem/31778  ✏️ 문제 설명  ✏️ 문제 풀이얼마 전 포스텍 open contest에 나왔던 문제입니다.군대에서 짜투리 시간 내서 참가해서 도전했었던 문제인데 계속 풀지를 못했던 문제입니다..분명 딱 봤을 때 투포인터랑 dp를 이용해야 한다는 거는 알았는데 11번 제출해서 모두 틀렸습니다 하하하 거두절미하고 문제 본론으로 넘어가보겠습니다.문자열을 교환하고 PPC 문자열을 만들 수 있는 개수를 출력해야 하는데, 교환은 최대 k번할 수 있습니다.이 말은 꼭 k번을 교환할 필요는 없다는 말입니다. 문자열 교환의 핵심은 P가 최대한 앞으로 C가 최대한 뒤로 가야 합니다.여기서 투 포인터 방식을 이용해서 교환을 해야 합니다. 자세한 내용은 코..

✏️ 문제 링크https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째www.acmicpc.net ✏️ 문제 설명  ✏️ 문제 풀이누적 합과 dp를 섞어서 푸는 문제입니다. 처음에는 그냥 브루투포스처럼 노가다로 돌리려고 했는데 연산 횟수가 4억번이라서 시간초과가 발생할 것 같아서 dp를 이용하기로 했습니다. 먼저 dp[200001][26]배열을 만듭니다. 이 dp 배열의 의미는d[i][j]라고 했을 때, i번째 문자열까지 j알파벳이 ..

✏️ 문제 링크 https://www.acmicpc.net/problem/25168 25168번: 게으른 아리를 위한 접종 계획 첫째 줄에 백신의 개수 N (1 < N ≤ 10,000)와 백신들의 선행관계 개수 M (1 ≤ M < 100,000)가 주어진다. 둘째 줄부터 M+1번째 줄까지 총 M개의 줄에 각 선행관계의 정보가 세 개의 정수 S,E (1 ≤ S < E ≤ N), www.acmicpc.net ✏️ 문제 풀이 위상정렬을 이용해서 풀었고 백신의 유효기간에 주의하여서 문제를 접근하였습니다. 이 부분에서 경우의 수가 나눠지게 됩니다. 두 백신간의 최소 대기기간이 일주일 이상 넘어가게 되는 경우와 그렇지 않은 경우로 나누어서 풀어야 합니다. 이것만 주의한다면 일반적인 위상정렬 문제와 다를게 없습니다...