비트마스크
-
SWEA 4168 : 삼성이의 쇼핑 ( 비트마스크 + 조합 연습 )백준 문제풀이/Dynamic Programming 2020. 5. 20. 14:00
문제 문제 풀어보기 (로그인 후 접속 가능) 풀이 냅색 문제에서 비트 마스크를 사용하여 선택한 물건들을 출력할 수 있도록 하였습니다. 냅색 알고리즘은 배낭문제에서 나온 기법인데 생각보다 자주 나오는 유형입니다. 최대의 만족도를 구하는 방법은 냅색을 이용해서 구하게 됩니다. 그리고 만족도를 인덱스로 하는 배열에 비트 마스크를 저장합니다. 출력 과정에서 정답이 되는 만족도에 있는 비트 마스크를 통해 어떤 옷을 선택했는지 출력합니다. 코드 #include #include #include #include using namespace std; int max(int a, int b) { if (a > b) return a; else return b; } int T; int ans; int n, m; int v[26..
-
BOJ 17142 : 연구소 3백준 문제풀이/GRAPH 2020. 5. 10. 21:39
문제 문제 풀어보기 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 간단하게 설명하면 모든 경우에 대해서 BFS를 전부 돌려봐야 하는 문제입니다. 어떤 바이러스를 활성화할 것인지를 고르는 방법이 포인트인데, 조합을 써도 되고 방법은 여러가지 입니다. 저는 비트 마스크를 사용해서 풀었으니 참고하시면 좋을 것 같습니다. 코드 #include #include #include #include #include #include using namespace std; int dx[] = { 1,-1,0,0 }; int dy[] ..