Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
반응형
문제
https://www.acmicpc.net/problem/3109
3109번: 빵집
유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던
www.acmicpc.net
풀이
solved.ac 난이도: Gold 2
DSF문제 중에서도 그리디 알고리즘으로 해결하는 문제이다.
항상 최선의 선택을 하는 그리디 방식으로 이번 문제를 해결하면,
다음의 세 가지 경로 선택 중에서 다음과 같은 우선순위를 정하면 된다.
1. 오른쪽 위를 방문
2. 오른쪽을 방문
3. 오른쪽 아래를 방문
이런 식으로 오른쪽 위를 항상 먼저 방문한다면 생성되는 파이프 라인을 최대한 오른쪽 위로 밀착시킬 수 있다.
다음 파이프 라인들도 생성이 완료된 파이프 라인에 최대한 위로 밀착시킨다면 아래의 파이프들이 연결될 수 있는 공간을 항상 최대로 만들 수 있다.
또한 이미 방문한 칸이지만 파이프가 설치되어있지 않다면 더 이상 방문해도 해당 경로에서 만들 수 있는 파이프 라인은 없으므로 방문하지 않은 곳만 방문하는 DFS를 구현하자.
코드
반응형
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No.5014 - 스타트링크 (C++, BFS) (0) | 2021.04.20 |
|---|---|
| [백준] No.10265 - MT (C++, SCC, Knapscak) (0) | 2021.04.19 |
| [백준] No.16915 - 호텔 관리 (C++, 2-SAT) (0) | 2021.04.14 |
| [백준] No.3648 - 아이돌 (C++, 2-SAT) (0) | 2021.04.14 |
| [백준] No.11281 - 2-SAT - 4 (C++, 2-SAT) (0) | 2021.04.13 |
댓글