문제 링크 http://icpc.me/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 비트마스크 dp문제다. dp[자릿수][마지막 수][사용한 수]로 정의하면 dp[i][j][k | (1

문제 링크 http://icpc.me/1657 풀이 비트 마스크를 하면서 dp를 돌면 된다. 백준[1648] 격자판 채우기와 거의 유사한 문제이다. 위의 문제와 차이점은 현재 칸을 안 채우고 넘어가는 경우가 있는 것이다. 코드 #include using namespace std; int dp[15 * 15][1 s[1]) swap(s[0], s[1]); if (s[0] == 'A') { if (s[1] == 'A') return 10; if (s[1] == 'B') return 8; if (s[1] == 'C') return 7; if (s[1] == 'D') return 5; if (s[1] == 'F') return 1; } else if (s[0] == 'B') { if (s[1] == 'B') r..

문제 링크 http://icpc.me/1648 1648번: 격자판 채우기 준규는 침대에 누워서 천장을 바라보고 있었다. 천장은 격자판 모양이었고, 계속해서 천장을 바라보다 보니 이런 생각이 들었다. 세로 크기가 N이고, 가로 크기가 M인 격자판을 2x1 크기의 도미노 www.acmicpc.net 풀이 비트 마스킹을 하며 dp를 돌면 풀 수 있다. 위와 같은 타일이 있을 때, k 번째 타일을 놓기 위해 필요한 정보는 k + 1 번째 타일이 채워져 있는지 여부와 k + 6(m) 번째 타일이 채워져 있는지 여부이다. 이와 같이 k번째 타일을 채우기 위해서는 m개의 타일 정보만 가지고 있으면 된다. 그렇기 때문에 m개의 타일 정보를 비트 마스킹하며 채워나가면 된다. 코드 #include #include int ..

문제링크 http://icpc.me/16991 풀이 비트마스크를 이용한 dp문제이며 외판원 순회와 다를 게 없다. 코드 #include #include #include using namespace std; using pii = pair; pii arr[17]; double dp[17][1

문제 링크 http://icpc.me/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 TSP(Traveling saleperson)라고 불리는 웰노운 문제다. 비트마스크와 dp를 이용하여 문제를 풀 수 있다. dp 정의는 dp[n][state] = 1부터 시작하여 state에 있는 점을 모두 지나 n번 노드까지 올 때 필요한 최소 비용으로 할 수 있다. 어느 정점에서 시작하던 사이클을 돌기 때문에 시작 정점은 고려할 필요가 없다. 나는 마지막 노드에서 0번..

풀이 dp[현재 사람][이전까지 수행한 일의 상태] = 현재 일의 상태까지의 최솟값 이 문제는 비트마스크와 dp를 이용하여 풀이할 수 있다. 이전까지 수행한 일의 상태를 0011 -> 1, 2번이 일을 한 상태와 같이 비트를 이용하여 상태를 표시한다. 코드 #include #include int d[22][22]; int dp[22][1 b ? b : a; } int dpf(int cur, int state) { int &ret = dp[cur][state]; //모든 일을 한 상황 ex) n = 3일때 1000 - 1 = 0111 if (state == (1

풀이 집합을 아래와 같이 비트로 표현 할 수 있다. {1, 2, 3, 4, 5} -> 11111 {2, 3, 4, 5} -> 11110 {1, 3, 5} -> 10101 i 번째 비트만 1로 바꾸기 == or 연산 set = set | (1 0010 i 번째 비트만 0로 바꾸기 == and 연산 set = set & ~(1 1111 & 1101 -> 1101 i 번째 비트만 뒤집기 == xor 연산 set = set ^ (1 1101 i 번째 비트가 1인지 0인지 확인 set & 1 0100 -> 결과값 != 0 -> i번째 비트가 1 코드 #include #include using namespace std; int main() { int M; scanf("%d", &M); int set = 0; whi..