본문 바로가기

비트마스크

 (7)
[백준 / BOJ] 17471 게리맨더링 문제 출처 : https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net N개의 선거구와 각 선거구에 사는 인원수가 주어진다. 선거구는 2개의 선거진영으로 나뉘며, 이때, 각 선거진영 선거진영 별로 모두 연결되어있어야한다. 이때, 선거진영의 인구수 차이를 최소화하는 값을 구하는 문제다. 풀이 비트마스킹을 이용한 완전탐색으로 푼 문제다. 처음엔 비트마스킹 + 백 트래킹으로 생각했으나, 이 방법으로는 모든 경우를 봐주지 못해서 풀기 힘들어 보였다. 알고리즘은 다음과 같다. 1. ..
[백준 / BOJ] 5852 Island Travels (Java) 문제 출처 : https://www.acmicpc.net/problem/5852 5852번: Island Travels Farmer John has taken the cows to a vacation out on the ocean! The cows are living on N (1
[백준 / BOJ] 1102 발전소 문제 출처 : www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이 www.acmicpc.net 은진이의 회사에는 N개의 발전소가 있다. 은진이가 회사에서 잘때마다 몇몇 발전소가 고장이난다. 이때, 고장난 발전소는 고장나지않은 발전소를 이용해 고칠수있으며, 일정한 비용이 발생한다. 적어도 P개 이상의 발전소가 고장나 있지 않도록 발전소를 고치는 최소비용을 구하는 문제다. 풀이 dp로 풀은문제다. 그리디로는 해결하지못하는데, 현재 경로가 더 많은 비용을 필요로 하더라도 결과적으로 더 작은 비용으로 발전소를..
[백준 / BOJ] 2098 외판원 순회 문제 출처 : www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고한다. 이때, 이미 방문한 도시는 재방문할수없다. 도시를 이동할때 일정한 비용이 필요할때, 외판원이 모든 도시를 거쳐 출발도시로 돌아오는 최소 비용을 구하는 문제다. 풀이 완전탐색으로 풀려고할경우, N이 최대 16이므로, 16 * 15 * 14 ..
[백준 / BOJ] 1029 그림 교환 문제 출처 : www.acmicpc.net/problem/1029 1029번: 그림 교환 첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에 www.acmicpc.net 사람들이 그림을 사고팔려고한다. 모든 그림 거래는 다음 조건을 만족해야한다. 1. 그림을 팔때, 그림을 산 가격보다 크거나 같은 가격으로 팔아야한다. 2. 같은 그림을 두 번 이상 사는 것은 불가능하다. 항상, 1번 사람이 그림을 0원에 샀다고했을때, 그림을 소유했던 사람의 수의 최댓값을 출력하는 문제다. 풀이 완전탐색으로 풀면, 최악의경우 첫 선택 = 15명 두번째 선택 = 14명 세번..
[백준 / BOJ] 1035 조각 움직이기 문제 출처 : www.acmicpc.net/problem/1035 1035번: 조각 움직이기 최대 5개의 조각이 있는 5*5 크기의 보드가 있다. 김지민은 조각을 적절히 움직여서 모든 조각이 연결 요소를 이루게 하려고 한다. 즉 상하좌우로 인접한 조각을 모두 연결했을 때, 모든 쌍의 조 www.acmicpc.net 5*5크기의 보드에 최대 5개의 조각이있다. 이 조각을 적절히 움직여서 모든 조각이 연결되도록 할려고한다. 조각은 상하좌우 한칸으로 이동시킬수 있다고할때, 모든 조각을 연결하는 최소한의 이동 횟수를 구하는 문제다. 풀이 처음에는(1년전??) BFS로 풀려했는데, BFS는 항상 최단경로를 보장하므로 하나의 조각을 기준으로 잡고 나머지 조각을 해당 조각으로 이동하는 횟수를 BFS로 구해주는로직을짰..
[백준 / BOJ] 1194 달이 차오른다, 가자. 제목 출처 : www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 민식이는 달이 차오르는 기회를 놓치지 않기 위해서 미로를 탈출하려고 한다. 한번 움직일때마다 수평 혹은 수직으로 한칸 움직일수있다. 민식이가 미로를 탈출하는데 걸리는 최소한의 이동횟수를 구하는 문제다. 미로에는 문이있고, 미로는 다음과 같이 구성되어있다. 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨) 벽 : 절대 이동할 수 없다. (‘#’) 열쇠 : 언제나 ..

티스토리툴바