코딩하기 좋은날

dp 문제입니다. 16개 이하의 발전소가 있을 때 이발전소를 주어진 P개를 켜야 하는 문제인데 발전소의 켜짐 꺼짐 유무를 확인하기 위해 비트마스킹을 이용하여 해결을 하여야 합니다. 2^16만큼 잡아서 dp[70000] 정도로 잡아주면 되겠습니다. 이때 발전소를 키기 위해서는 켜진 발전소를 이용하여 꺼진 발전소를 키므로 각 함수에서 꺼진 발전소를 찾고 얘를 켤수 있는 발전소를 찾아서 재귀를 돌면 됩니다. 이때 cost가 0인것은 진짜로 0인 것이지 킬 수 없는게 아니라는 점(처음에 못키는줄 알았습니다.) 생각하면서 해결하면 됩니다. 외판원 순회문제와 유사한데 좀더 간단한(?) 문제 같습니다. 다음은 코드입니다. #include #include #include #include #define INF 98765..

DP 문제입니다. 이전에 풀었던 환상의 듀엣 이란 문제와 유사한데 경찰차가 이동하는 지점이 반드시 정해져 있습니다. 즉 두 경찰차는 반드시 시작지점이 아니면 사건이 발생한 어느지점에 위치하고 있기 때문에 DP 배열을 아래와 같이 정의 할 수 있습니다. DP[i][j] = 1번 경찰차가 마지막으로 해결한사건(i), 2번 경찰차가 마지막으로 해결한사건(j) 일때의 최소 이동거리 저렇게 정의한다면 우리는 max(i,j) + 1이 다음사건임을 알 수 있습니다. 이 문제는 여기서 끝이 아니라 이 최소비용을 얻었을때 각 사건을 어떤 경찰차가 해결하였는지 까지 출력을 하여야 합니다. 처음에 이 경로를 어떻게 구해야 할지 생각이 안났는데 먼저 최소 비용을 구한 후 다시 0,0 부터 시작하며 자신이 선택한 경로를 따라가..

https://www.acmicpc.net/problem/17069 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 초기에 1,2에있는 파이프를 이리저리 옮겨 끝좌표 까지 갈수있는 경우의 수를 구하는 문제입니다. 각각 가로 세로 대각선일때 이동가능한 방향과 조건들이 주어져있습니다. 파이프 옮기기 1같은경우는 bfs나 dfs로도 해결이 가능하였을걸로 아는데 옮기기 2는 N의 크기가 커져서 dp를 사용하여 풀어야 합니다. dp배열은 우선 좌표정보와 좌표에서 상태를 저장해야하므로 3차원으로 잡고 상태 같은 경우는 0,1,2 순으로 가로,세로,대각선으로 정했습니다. dp식은 크게 어려울것이 없습니다. 현재 좌표가 i,j라하면 dp[i+1][j][0] = dp[i][j+1][0] = dp[i][j]..

https://www.acmicpc.net/problem/17135 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 적들이 주어진 맵에 존재하고 성벽에 궁수 3명이 있을때 궁수들의 위치를 배치하여 가장 적을 많이 처치 할 수 있는 수를 구하는 문제입니다. 모든 가능한 궁수들의 배치에 대하여 각각 시뮬레이션을 해보면 됩니다. 주어진 조건에 따라 현재 제거할 수 있는 가장 가까운 적(거리가 가장가까운)들을 차례대로 제거하고 적들을 한칸씩 아래로 내리면서 더이상 적이 없을때까지 진행해주시면 됩니다. 저는 벡터에 적들의 좌표를 유지시키면서 풀었습니다. 다음은 코드입니다. #include #include #include #include using namespace std; int N,M,D; int..

https://www.acmicpc.net/problem/12920 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이문제는 평범한 배낭1의 업그레이드(?) 문제입니다. 아마 이문제 푸시는 분들은 평범한 배낭1문제를 푸셨을 거라고 생각하는데요. 두문제의 유일한 차이는 물건의 개수입니다. 이문제 같은 경우 물건의 개수가 여러개 일 수 있습니다. 따라서 각각 경우를 모두 고려해주어야 하는데 어떻게 해야할지 생각이 잘 안나서 다른 분들의 풀이를 참고 하였습니다. 가장 중요한 아이디어는 사용할 수 있는 물건의 개수를 2의 제곱수의 합으로 분리 시키는 것입니다. 예를 들어 A라는 물건이 7개 있다면 각각 1개 / 2개 /4개의 물건으로 분리시키고 그에 맞는 만족도를 저장합니다. 이런식으로 분리시키면 각각 1,..

https://www.acmicpc.net/problem/10942 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 수열이 주어졌을때 구간에 대한 팰린드롬 여부를 출력해야 하는 문제입니다. 수열의 길이는 2000 이고 총 100만개의 쿼리가 들어오므로 모든 구간에 대한 팰린드롬 여부를 미리 구해놓아야 합니다. 따라서 저는 2차원 dp배열을 선언하고 재귀함수를 호출하는 식으로 구했습니다. 길이가 1일때와 2일때는 미리 구해야 하는데 길이가 1인경우는 항상 팰린드롬이므로 1을 저장합니다. 길이가 2일때는 두문자가 같다면 팰린드롬이므로 1을 저장하고 그렇지 않으면 팰린드롬이 아니므로 0을 저장합니다. 이후 구간의 양끝에서부터 길이를 줄여나가면서 찾으면 됩니다. 현재 함수에서 보는 구간이 s,t라..

https://www.acmicpc.net/problem/2248 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 이전에 쓴 1256 사전과 유사한 문제입니다. N자리의 이진수가 있을 때 L개 이하의 1이 존재가능 하다고 할 때 이중에서 I번째 순서의 이진수를 찾는 문제입니다. I는 범위안에 있도록 주어진다 했으니 최대 가능한 I가 2^31번째 일것입니다. 따라서 이전의 사전 문제처럼 dp를 이용하여 개수들을 저장하고 skip하는 방식으로 해결을 하여야 합니다. dp배열에는 이항계수 성질인 nCk = n-1Ck-1 + n-1Ck 를 이용하여 n개의 비트중 1이 k개일때를 저장 했습니다. dp[n][k] = dp[n-1][k-1] + dp[n-1][k] 이렇게 저장 한뒤 원하는 이진수를 찾는..

https://www.acmicpc.net/problem/1256 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 a와 z로만 이루어진 단어가 사전순으로 정렬 되있을때 K번째 단어를 찾는 문제입니다. a,z가 최대 100개이고 K가 10억개이므로 단순히 개수를 세는 방법으로 해결이 불가능합니다. 문제를 해결하기 위해서 저는 먼저 2차원 배열에 a가 i개 z가 j개 있을때 나오는 조합의 개수를 저장하였습니다. 식을 세워보면 dp[i+1][j] = dp[i][j] * (i+j+1) / (i+1) dp[i][j+1] = dp[i][j] * (i+j+1) / (j+1) 과 같은 식으로 개수를 구할 수 있습니다. 각 조합의 개수를 구한다음 이제 K번째 단어를 찾아야 하는데 문자를 앞에서부터 하나씩 ..