스위핑

[백준 2836] 수상 택시 (C++)

2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 그리디인줄 알고 삽질을 오래 했다. 스위핑 문제였다. 시간이 녹았다 하지만 스위핑을 제대로 되새길 수 있었다! 역방향 이동거리 * 2 == 초록색으로 표시된 거리 * 2 -> 되돌아 가서 승객을 내려주기 + 되돌아 가기 전 위치로 복귀 ANSWER : M + 위 값들의 합 스위핑 문제임을 파악하고 좌표의 left, right 값을 잘 설정해주자. #include #include #include #include #include #define fasti ios_b..

[백준 20928] 걷는 건 귀찮아 (C++)

20928번: 걷는 건 귀찮아 일직선 위에 놓인 $N$개의 지점 $p_i$에는 최대 $x_i$만큼 이동시켜주는 인력거꾼들이 있다. 즉, $p_i$에 있는 인력거꾼은 $p_i$, $p_i+1$, $p_i+2$, $...$, $p_i+x_i$ 중 한 지점까지 승객을 데려다준다. 세상 www.acmicpc.net 1. 현재 인력거에서 M까지 갈 수 있는지 확인한다. M까지 갈 수 있다면 결과 값을 최솟값으로 갱신한다. 2. 현재 인력거에서 갈 수 있는 인력거들을 모두 queue에 넣는다. 이때 가장 멀리있는 인력거 위치 이후부터 찾는다. 인력거를 찾게되면 그때마다 가장 멀리있는 인력거의 위치를 갱신해준다. 알고리즘 과정 입력 4 10 1 3 5 7 4 6 5 2 파란색 동그라미는 인력거의 위치를 의미한다. 파..