Dist(치킨집, 거리) 객체 생성
dists[i][x] = Dist(j, dist)
-> 집 i와 치킨집 j 사이 거리가 dist
각 dists[i]들을 dist 오름차순 정렬
치킨집 선택하면서 DFS 조합
M 개의 치킨집 선택 시
각 dists[i]들에서 가장 앞의 선택된 치킨집의 dist 합 계산
최소값 갱신
Q + 1 조각을 만들 때 가장 작은 조각 길이 최대값
= Q + 1 조각을 만들 수 있는
조각 길이 최소 한계값의 upperBound - 1
특정 길이가 최소 한계값일 때
Q + 1 조각을 만들 수 있는지 확인하면서 이분 탐색
Q가 오름차순이므로 이전 upperBound를 right로 사용
정현우 BOJ 17144 미세먼지 안녕!
풀이
map 1 차원 변환 미세먼지 확산 4방 탐색 diff[][]에 확산값 저장 후 확산값 일괄 적용 공기청정기 작동 흡입구부터 배출구 까지 흡입 방향으로 한 칸씩 이동 배출구 미세먼지 0
정현우 : BOJ 15686 치킨 배달
풀이
Dist(치킨집, 거리) 객체 생성 dists[i][x] = Dist(j, dist) -> 집 i와 치킨집 j 사이 거리가 dist 각 dists[i]들을 dist 오름차순 정렬 치킨집 선택하면서 DFS 조합 M 개의 치킨집 선택 시 각 dists[i]들에서 가장 앞의 선택된 치킨집의 dist 합 계산 최소값 갱신
정현우 : BOJ 14503 로봇 청소기
풀이
청소되지 않은 빈 칸을 찾을 때까지 반시계 회전 청소되지 않은 빈 칸 찾으면 전진 후 청소 못 찾으면 후진, 벽이면 작동 멈춤
정현우 : BOJ 1182 부분수열의 합
풀이
1 ~ (1 << N) - 1 비트마스크 부분집합 dp[i] = 숫자 i가 나타내는 부분집합의 숫자들의 합 dp[i] = dp[i - lowestOneBit(i)] + dp[lowestOneBit(i)] 값이 S인 dp[i]의 개수
정현우 : BOJ 17179 케이크 자르기
풀이
Q + 1 조각을 만들 때 가장 작은 조각 길이 최대값 = Q + 1 조각을 만들 수 있는 조각 길이 최소 한계값의 upperBound - 1 특정 길이가 최소 한계값일 때 Q + 1 조각을 만들 수 있는지 확인하면서 이분 탐색 Q가 오름차순이므로 이전 upperBound를 right로 사용