문제 풀이 그래프 탐색, 누적합 문제이다. 횡단보도의 칸 중에서 물이 빠질 칸을 BFS로 탐색한다. BFS의 시작은 하수구 칸에서 시작한다. 현재 탐색 중인 칸의 상하좌우 칸 중에서, 현재 칸의 높이 이상인 칸은 물이 빠진다. 신발을 딛을 수 있는 방법의 수는 2차원 배열의 누적합으로 구한다. 위의 그림에서 초록색 영역의 합을 구해보자. 파란색 영역을 모두 한번씩 더한다면 빨간색 영역은 두 번 더해진다. 그러므로, 파란색 영역을 한번 더하고, 빨간색 영역을 한번 빼면 초록색 영역의 합을 구할 수 있다. for (int i = 1; i N >> M; cin >> h >> w; for (int i = 1; i road[i][j]; } } memset(water, true, sizeof(water)); int..
문제 풀이 누적 합과 이분 탐색을 사용한다. 피자 조각의 최대 개수는 1000개 이므로 O(N * N)으로 해도 시간초과가 발생하지 않는다. A와 B에서 얻을 수 있는 모든 피자 조각을 계산한다. 피자 조각은 끝과 처음이 연결될 수 있으므로 유의해서 더해야 한다. A에서 얻을 수 있는 피자 조각을 기준으로 P와의 차이만큼의 B의 피자 조각의 수를 이분 탐색으로 구한다. 코드 #include #include #include using namespace std; vector A; vector A_parts; vector B; vector B_parts; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int P; int m,..
문제 풀이 누적 합과 이분 탐색을 사용한다. 배열 A에서 얻을 수 있는 모든 부 배열의 합을 vector A에 저장한다. 배열 B에서 얻을 수 있는 모든 부 배열의 합을 vector B에 저장한다. 이분 탐색을 위해 vector B를 오름차순으로 정렬한다. upper_bound와 lower_bound로 (T - 현재 검사하는 vector A의 원소의 값)을 가지는 vector B의 원소의 수를 구한다. upper_bound는 현재 검사하는 벡터에서 N의 값을 초과하는 값의 첫 인덱스를 반환한다. lower_bound는 현재 검사하는 벡터에서 N의 값 이상의 값의 첫 인덱스를 반환한다. 코드 #include #include using namespace std; int A[1001]; vector sum_A..
