[Codeforces 1084B] Kvass and the Fair Nut N개의 음료수의 용량(v_i)과 s가 주어진다. 각각의 음료수에서는 최소 0부터 최대 (v_i)까지 음료수를 빼낼 수 있다. 이렇게 음료는 빼내서 s가 되도록 만들어야 한다. 이때 가장 적게 든 음료수의 용량이 최대가 되도록 하는 문제이다.처음 딱 봤을 때는 당연히 바이너리 서치로 푸는 문제 인 줄 알았다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include#includeusing namespace std;typedef long long ll;int fMax(ll a,ll b){ return a>b?a..
[Codeforces 1084C] The Fair Nut and String 난이도 1500짜리라서 얕봤다가 호되게 당한 문제이다. 처음에 버추얼로 돌 때는 10분만에 솔루션은 나왔는데 그것과 관련된 개념을 잘 몰라서 못 풀었다. 일단 결론부터 얘기하자면 이 문제는 b를 기준으로 분할했을 때, 연속해서 등장하는 a의 개수들이 있을텐데 그 개수로 집합의 원소로 구성해서 그 집합의 모든 부분집합의 곱들의 합이 곧 답이다. 예를 들어 설명하자면 " abaabaaa " 라는 문자열이 있다면 b를 기준으로 a의 개수를 {1,2,3}이 된다. 그래서 {1,2,3}으로 만들 수 있는 부분집합들의 원소들의 곱들의 합(=23)이 답이 된다. 이 연산을 단 O(N)만에 수행하는 공식이 존재하는데 나는 몰라서 naive하게..
[Codeforces 1093D] Beautiful graph 그래프 문제를 풀 때는 항상 Disjoint된 상태를 고려해야한다는 교훈을 일깨워준 문제. 그래프의 vertex에 1,2,3중에 하나의 숫자를 부여해야 하는데, edge로 연결된 두 vertex끼리는 두 수의 합이 반드시 홀수가 되게 만들어야 한다. 이 조건을 만족하게 숫자를 부여하는 방법의 경우의 수를 구하는 문제이다.내가 우선 생각한 것은 두 수를 더해서 홀수가 되도록 만드는 방법이었다. 두 수를 더해서 홀수가 되게 하려면 (짝수+홀수) 의 방법밖에 존재하지 않는다. 이 문제에서 사용할 수 있는 짝수는 2밖에 없고, 홀수는 1,3밖에 없다. 그래서 나는 그래프를 구성한 뒤 dfs를 돌면서 각 노드마다 번갈아가면서 홀->짝->홀->짝... ..
[BOJ 2618] 경찰차 이 문제도 앞서 봤던 카드 게임처럼 선택에 따른 결과가 달라지는 유형의 문제이다. 어떤 i번째 사건이 있을 때, 그 사건에 1번 경찰차가 출동할 것이냐 2번이 출동할 것이냐에 따라서 달라지기 때문이다. 그래서 dp테이블도 'dp[fir][sec]=cost -> 첫 번째 경찰차가 fir에 위치하고, 두 번째가 sec에 위치할 때 앞으로 모든 사건을 처리하기 위해 이동해야 하는 총 이동거리=cost'가 된다. 그리고 마지막에는 총 이동거리와 함께 각 사건별로 출동한 경찰차의 번호도 출력해야 하는데 이는 최종거리를 토대로 거꾸로 빼나가면서 추적해나가면 된다. 마치 기업투자 문제랑 비슷하다. 1234567891011121314151617181920212223242526272829303..
[BOJ 11062] 카드 게임 이 문제를 풀면서 재귀함수를 이용한 탑다운 dp가 훨씬 편리하다는 것을 뼈저리게 느꼈다. 예전부터는 dp문제를 모두 for문으로 짜려고 고집했는데 이제부터는 재귀함수를 자주 활용해야겠다. 선택의 여지에 따라서 앞으로의 결과가 달라지는 유형의 문제를 이 방식으로 풀면 편하다. 이 문제의 경우, 왼쪽의 카드를 뽑을 것이냐 오른쪽의 카드를 뽑을 것이냐 이렇게 두 가지의 선택지가 있는 것처럼 말이다. 이 문제에서 한가지 막혔던 부분은 나의 최적의 경우와, 상대의 최적의 경우를 어떻게 동시에 고려하느냐였는데 나의 최적일 때는 max를 취하고, 상대의 최적일 때는 min을 취하면 된다. 나의 min의 경우와 상대의 max의 경우가 곧 동치이기 때문이다. 1234567891011121..
[BOJ 1695] 팰린드롬 만들기 이 문제도 약 5시간정도 고민해서 풀었다. 이 문제를 풀면서 느낀 점은, dp유형의 문제는 현재상태와 이전상태가 어떤 관계를 통해서 서로 연결될 수 있는지를 규명하는게 중요하다는 점이다. 팰린드롬의 경우 단순히 dp[a][b]=dp[a][c]+dp[c][b]가 성립할 수 없는게 팰린드롬인 두 수열 '121'과 '232'를 서로 붙인 '121232'는 팰린드롬이 아니기 때문이다. 그래서 dp를 활용하기 위해서는 이전상태를 어떻게 이용할까를 고민하고 디자인하는게 중요하다. 그래서 문제에 등장하는 '특징'이 무엇일까를 잘 찾아내야 한다. 즉 문제에서 팰린드롬의 '특징'을 dp와 결부시켜야 하는 것이다. 그 특징이란 팰린드롬에서 dp[a][b]=dp[a+1][b-1]과 밀접한..
[BOJ 1328] 고층 빌딩[BOJ 8895] 막대 배치 (위 문제와 거의 비슷함) 4일, 시간으로 따지면 7시간 정도 고민한 문제인데 풀릴 듯 안 풀려서 솔루션을 찾아보았다. dp테이블의 의미까지는 dp[n][l][r]=a n번째 막대까지 왼쪽에서 봤을 때 l개, 오른쪽에서 봤을 때 r개일때 가능한 경우의 수 a가지 까지는 똑같이 생각했으나 나머지 점화식을 떠올리지 못했다. 풀이의 핵심은 막대의 길이를 내림차순(긴 막대 -> 짧은 막대)으로 본다는 것이었다. 만약 현재 dp[i][l][r]의 테이블을 채우기 위해서는 이전 막대의 l과 r이 1 작은 값의 경우의 수와 일치한다는 것이다. 이게 가능한 이유는 막대를 내림차순으로 사용하기 때문에, 현재 사용한 막대는 반드시 이전 막대들보다 짧다는 확신이 있..
[BOJ 2281]데스노트 이 문제는 두 가지 방법으로 풀었는데 내가 처음으로 풀었던 방법은 시간이 더 오래 걸렸다. 그래서 시간이 짧은 다른 풀이로 한번 더 풀었다. 두 풀이 모두 dp를 기초로 하는 풀이기는 하지만 dp테이블의 의미가 달랐다. 내가 처음으로 푼 방식은 구간별로 길이의 합과 그 합을 m에서 뺀 값의 제곱을 미리 다 구해놓았다. 그 값들을 바탕으로 3중 for문을 돌았기 때문에 시간 복잡도는 거의 O(N^3)이라고 할 수 있다. N=1000이기 때문에 거의 터질 수도 있는 풀이지만 온전히 N^3을 도는 것은 아니라서 시간 안에 들어온 것 같다. 이 풀이의 경우 dp[a][b]=c의 의미는 'a부터 b번 째 이름 전까지(표기상으로 '[a,b)')의 합으로 만들 수 있는 최소 공백의 제곱의 ..