그리디

[백준 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 파란색 동그라미는 인력거의 위치를 의미한다. 파..

[백준 1826] 연료 채우기 (C++)

1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 처음에 DP 문제인줄 알고 DP로 접근을 시도했었다. dp[현재 이동한 거리][현재 가지고 있는 연료 양] 을 두면 top down DP를 통해서 쉽게 구할 수 있을거라고 생각했었다. 근데 L이 최대 100만이고 연료 양도 최대 100*10000 라서 DP 배열 자체를 할당할 수가 없었다. N과 L이 너무 커서 이건 무조건 그리디라고 생각했고 실제로 그리디로 풀수가 있었다. 1. 현재 연료를 모두 소진할 때까지 쭉 달린다. ..

[백준 14595] 동방 프로젝트(Large) (C++)

14595번: 동방 프로젝트 (Large) 첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다. www.acmicpc.net x ~ y 사이의 모든 방은 통합해서 하나의 방으로 만든다. 통합하는 순서는 결과에 영향을 주지 않기 때문에 x가 작은 순으로 오름차순 정렬한다. 현재 통합한 y 좌표의 최댓값보다 새로 통합할 방의 x좌표가 더 크다면, ((새로운 x) - (이전 y)) 값 만큼 방의 개수가 늘어난다는 뜻이다. 만약 새로운 x의 좌표가 현재 y보다 작다면 새로운 방은 더 생기지 않는다. N에서 y의 최댓값을 뺀 값을 ..

[백준 2262] 토너먼트 만들기 C++

2262번: 토너먼트 만들기 월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러 www.acmicpc.net 그리디 랭킹이 높은 사람이 반드시 이기기 때문에 우승자는 항상 1번이다. 부전승이 여러번 있어도 상관없기 때문에 매번 가장 랭킹이 낮은 사람(번호가 높은 사람)만 경기를 하게 했다. 랭킹이 가장 낮은 사람(자신)의 양 옆 사람 중에서 자신과 랭크 차이가 적게 나는 사람과 경기를 치러야 한다. 랭크 차이가 많이 나는 사람과 경기를 치르게 되면 그 사람은 랭크차이가 많이 나는 만큼 경기를 더 많이 치러야 하기 때문이다. 경기를 더 많이 한다면 그만큼 최솟값과는 멀어질 수..

[백준 8980] 택배 C++

8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 그리디 | 정렬 1. 문제 해결 아이디어 [백준 1700] 멀티탭 스케줄링 C++ 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면 hyeo-noo.tistory.com 위 문제와 비슷한 느낌이다. 미래에 배송될 정보들을 모두 알고 있으므로 마을에 도착해서 박스를 받을 때마다, 먼저 도착하는 마을에 배..

[백준 1700] 멀티탭 스케줄링 C++

1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 그리디 알고리즘 OS page replacement policy 중 하나인 Optimal replacement policy 를 적용하는 문제이다. 미래에 어떤 작업을 할 지 다 알고있는 경우이므로 적용이 가능하다 -> 가장 나중에 사용될 작업을 현재 멀티탭에서 뽑는다 (2021/05/16 update) 이 문제에서도 특정 조건이 부합하는지만 알면 언제나 최적의 해를 구할 수 있다 특정 조건을 찾는게 많이 어려웠음.. 특정 조건 : ex) 3구짜리 멀티탭이 있고 ..

[백준 3109] 빵집 C++

3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 이 문제는 그리디 알고리즘을 적용한 DFS문제이다 그리디를 어떻게 적용하는가?? 항상 오른쪽 위 부터 탐색을 해야한다(0번째 Row부터 탐색할 경우만 해당. R-1번째 부터 탐색하면 오른쪽 아래부터 탐색) 탐색을 한 부분은 다시 탐색하지 않는다! (DP개념도 같이 적용) 문제를 이해했다면 항상 오른쪽 위 부터 탐색해 간다는건 쉽게 이해할 수 있다 나도 처음엔 이것만 생각해서 백트래킹 방식을 적용해 37 번 라인에 방문했던 곳을 초기화 해주는 코드(Map[r][c] = 0;)가 ..