본문 바로가기
반응형

비트마스킹12

백준 14391번 종이 조각 - C++ 풀이 1. 각 칸을 세로로 사용할지 가로로 사용할지 결정한 뒤, 전체 조각의 합을 구한다. 2. 모든 경우 중 전체 조각의 합이 가장 큰 경우를 고른다. 1. 각 칸을 세로로 사용할지 가로로 사용할지 결정한 뒤, 전체 조각의 합을 구한다. 모든 칸에 대해 각 칸을 세로 조각으로 사용할지, 가로 조각으로 사용할지 결정한다. 결정 결과를 비트 마스킹으로 나타낼 수 있다. (ex. 가로는 1 세로는 0) 모두 결정한 뒤에는 전체 조각의 합을 구하면 된다. 전체 조각의 합을 구할 때, 인접한 두 칸 A, B가 똑같이 가로 또는 세로 칸일 경우, A와 B는 서로 이어져 있는 긴 조각으로 처리해주어야 한다. 2. 모든 경우 중 전체 조각의 합이 가장 큰 경우를 고른다. 모든 경우를 고려한 뒤 그 중 합이 가장 큰 경우를.. 2022. 8. 23.
백준 18809번 Gaaaaaaaaaarden - C++ 풀이 1. 배양액을 뿌리는 모든 경우를 고려하여 피울 수 있는 꽃의 최대 개수를 찾는다. 2. BFS를 사용하여 배양액의 전이를 시뮬레이션한다. 1. 배양액을 뿌리는 모든 경우를 고려하여 피울 수 있는 꽃의 최대 개수를 찾는다. 배양액을 뿌릴 수 있는 땅의 개수가 최대 10개이고, 뿌려야 하는 배양액의 개수도 최대 10개이므로, 최대 배양액을 뿌리는 경우의 수는 최대 10C5 = 252가지 밖에 없다. 또한 각 경우를 O(N^2)에 시뮬레이션할 수 있으므로 브루트 포스를 사용해도 충분하다. 배양액을 뿌릴 곳을 선택할 때는 비트 마스킹을 사용하였다. 초록과 빨강 배양액을 뿌릴 곳을 각각 G, R개를 선택하고, 두 색깔이 겹치는 곳이 있는지 확인해주었다. 2. BFS를 사용하여 배양액의 전이를 시뮬레이션한다. 배.. 2022. 7. 27.
백준 4991번 로봇청소기 - C++ 풀이 1. 총 이동 횟수가 최소가 되는 순서로 더러운 칸들을 방문해야 한다. 2. A칸에서 B칸으로 가기 위한 최소 이동 횟수는 BFS로 구한다. 1. 총 이동 횟수가 최소가 되는 순서로 더러운 칸들을 방문해야 한다. 더러운 칸이 최대 10개이므로, 더러운 칸을 방문하는 순서를 정하는 경우의 수는 10! 이 중 총 이동 횟수가 최소가 되는 경우를 찾으면 된다. N이 작기 때문에 DFS를 이용한 브루트 포스로도 시간 내에 통과가 가능한데, 아래 코드에서는 DP를 사용하였다. 2. A칸에서 B칸으로 가기 위한 최소 이동 횟수는 BFS로 구한다. 중간에 장애물이 있을 수 있으므로 A칸에서 B칸으로 가기 위한 최소 이동 횟수는 BFS를 이용해서 구해야 한다. #include #include #include #incl.. 2022. 7. 14.
백준 1311번 할 일 정하기 1 - C++ 풀이 1. dp(idx, mask): 사람들의 상태가 mask일 때, idx~마지막 일까지 수행하기 위한 최소 비용 2. dp(idx, mask) = min(i번 사람에게 맡겼을 때의 비용 + dp(idx+1, mask | (1 2022. 7. 12.
백준 1029번 그림 교환 - C++ 풀이 1. dp(curr, price, mask) = 현재 curr이 price원에 그림을 가지고 있고 지금까지 그림을 산 사람들이 mask일 때, 더 그림을 소유할 수 있는 사람 수의 최댓값 2. dp(curr, price, mask) = max(1, 1 + dp(next, nextPrice, newMask)) 1. dp(curr, price, mask) = 현재 curr이 price원에 그림을 가지고 있고 지금까지 그림을 산 사람들이 mask일 때, 더 그림을 소유할 수 있는 사람 수의 최댓값 dp(curr, price, mask)를 위와 같이 정의하자. 사람은 최대 15명, 가격은 최대 9원이므로 총 구해야 하는 dp값은 15*10*(2^15) 개. 2. dp(curr, price, mask) = max.. 2022. 7. 3.
반응형

티스토리툴바