문제 예제 예제 1에서는 첫 번째 보석을 담았을 때가 최대이고, 예제 2에서는 첫 번째 보석을 두 번째 가방에, 세 번째 보석을 첫 번째 가방에 담았을 때가 최대이다. 구현 1 - 시간 초과 💡 보석을 가격이 높은 순으로 정렬, 가방은 무게가 작은 순으로 정렬하고 비싼 보석부터 차례대로 가방에 담는다 우선순위 큐를 사용하면 자동으로 정렬이 되므로 보석 정보를 priority_queue에 담아주었다. 보석을 담을 수 있는 가방을 찾기 위해 반복문을 사용하였는데, 이 때 한 가방에 2개의 보석이 담기지 않도록 visited 배열을 추가로 사용해주었다. #include using namespace std; int n, k; // 보석과 가방의 개수 priority_queue v; // {보석 가격, 무게} v..

최근 DFS나 백트래킹 유형을 풀 때 재귀 함수를 구현하는 것이 어려워서 당분간은 재귀 유형을 풀면서 재귀 연습을 하고자 한다! 이번에 풀 문제는 백준 1780번 종이의 개수라는 문제이다. 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 설명 예제 설명 구현 아이디어 전체 구현 과정 1. 모두 같은 수 A라면 A로만 채워진 종이의 개수를 +1한다 2. -1, 0, 1로 채워진 종이의 개수를 구하기 위해 map을 사용 (ex. 각각 3, 2, 1장일 때 { (-1,3), (0,2), (1,1) ..

1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 문제 설명 뒷면이 위를 향하는 동전 개수를 최소로 해야 하니 T가 최소일 때를 T의 개수를 구해야 한다. 예제 설명 위 그림처럼 2번째 행을 뒤집고 > 3번째 열을 뒤집으면 T가 2개가 되는데 이 때가 T가 최소일 때이므로 2가 출력된다 시간 복잡도 N은 최대 20까지 가능하며, 행이나 열을 뒤집을 수 있기 때문에 모든 경우의 수를 생각했을 때 총 연산 횟수는 2^(20+20) = 2^40번일 것이다. 2^40번이라면 시간 초과가 날 것이다. 하지만, 이 때..

방금 배운 비트마스킹 을 활용하여 백준 문제를 풀어보자! 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 문제 설명 예제 1번은 식재료 1, 3, 5를 골랐을 때이고, 2번은 식재로 2, 3, 4를 골랐을 때이다. 둘 다 최소 영양성분 100, 70, 90, 10 이상을 만족하지만 총 가격은 1번이 270, 2번이 180으로 2번을 골랐을 때가 가격이 더 저렴하므로 더 나은 선택이 된다. 구현 아이디어 각 재료의 선택 여부를 0과 1로 나타내면 6자리 이진수로 모든 경우의 수를 나타낼 수 있다. ex) 111..

4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 문제 설명 예제 아래 사진은 시간별 지훈이(왹깅)와 불(🔥)의 위치를 나타낸 그림이다. 이 때 주의할 것은 지훈이와 불이 '동시에' 움직인다는 것이다. 지훈이가 움직인 다음 불이 붙거나, 불이 붙은 다음 지훈이가 움직이는 것이 아니다. t=2일 때 미로의 가장자리에 도착하였고, 한 칸을 더 움직여 t=3일 때 지훈이는 미로를 탈출할 수 있다. 구현 아이디어 처음에는 지훈이가 움직일 수 있는 경로가 여러 개라고 생각해서 DFS로 완전탐색을 해야 한..

문제 설명 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제에서 중요한 부분들을 하이라이트로 표시해보았다. 이제 예제를 통해 문제를 좀 더 확실히 이해해보자. M=3인데 치킨집(2)의 개수가 3개이므로 폐업을 시킬 필요가 없다. (1,3) ~ (2,3) 사이 치킨 거리 = 1 (3,2) ~ (3,3) 사이 치킨 거리 = 1 (3,3) ~ (4,3) 사이 치킨 거리 = 1 (2,3) ~ (2,5) 사이 치킨 거리 = 2 이므로, 도시 전체의 치킨 거리는 5이다. 구현 아이디어 치킨집 중 ..