[Codeforces 1084C] The Fair Nut and String 난이도 1500짜리라서 얕봤다가 호되게 당한 문제이다. 처음에 버추얼로 돌 때는 10분만에 솔루션은 나왔는데 그것과 관련된 개념을 잘 몰라서 못 풀었다. 일단 결론부터 얘기하자면 이 문제는 b를 기준으로 분할했을 때, 연속해서 등장하는 a의 개수들이 있을텐데 그 개수로 집합의 원소로 구성해서 그 집합의 모든 부분집합의 곱들의 합이 곧 답이다. 예를 들어 설명하자면 " abaabaaa " 라는 문자열이 있다면 b를 기준으로 a의 개수를 {1,2,3}이 된다. 그래서 {1,2,3}으로 만들 수 있는 부분집합들의 원소들의 곱들의 합(=23)이 답이 된다. 이 연산을 단 O(N)만에 수행하는 공식이 존재하는데 나는 몰라서 naive하게..
[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)')의 합으로 만들 수 있는 최소 공백의 제곱의 ..
[BOJ 2568]전깃줄-2 알고리즘 분류상으로 LIS로 되어있기 때문에 어렵지 않게 풀기는 했다만, 만약 분류를 모른 상태로 접했다면 어떻게 풀어야 할지 고생했을 문제이다. 이런 부류의 문제를 풀 때는 어떻게 LIS로 푸느냐 보다는, 왜 이 문제가 LIS로 풀릴 수 있는지를 파악하는 것이 더 중요하다. 전깃줄1 문제도 있는데, 없애야 할 전선의 최소 개수를 구하는 것은 같지만 2는 거기서 구체적으로 몇 번째의 전선을 없애야 하는지를 더 구해야한다. 게다가 N이 최대 10만으로 늘어났기 때문에 LIS를 구하는 알고리즘도 O(NlogN)만에 구해야 한다. 사실 구하는 법을 까먹어서 예전 소스를 슬쩍 보고왔다. 우선 왜 이 문제가 LIS에 해당하는지부터 알아보자. 이 문제에서 핵심은 전선끼리 교차하는 경우가..
[BOJ]2662-기업투자 예전부터 시도해왔던 문제인데 이제서야 풀었다. 전형적인 dp문제로, 각 기업별로 투자금별 수익금이 제시되고 한정된 금액으로 최대의 수익을 내기 위해서 어느 기업에 얼마만큼 투자를 해야하는지 묻는 문제이다. dp테이블의 의미는 dp[a][b]=c -> 금액 a원을 b번째 기업까지 투자했을 때 만들 수 있는 최대 금액 c원이다. 나 같은 경우에 최대 수익금을 찾는 구현은 그럭저럭 잘 했으나 각 기업에 얼마만큼 투자를 했는지 찾는 과정의 구현이 조금 애를 먹었다. dp loop를 돌리는 동안에 별도로 add[][]라는 배열을 마련해서 이전 상태에서 현재상태의 얼마를 더 투자해서 현재의 금액이 되었는지를 저장하는 역할이다. 그리고 최대 금액을 알아낸 상태에서 역순으로 금액을 빼가면서 ..