🥇 Problem Solving/Greedy

[Python] BOJ / 13305번 / 주유소

13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 📝 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이..

[Python] BOJ / 2812번 / 크게 만들기

2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 📝 풀이 N자리 숫자가 주어졌을 때, 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램 전체 자릿수에 대해서 아래 과정을 반복한다 스택에 i번째 자릿수 값을 저장 숫자 제거 횟수가 남아 있고(del_cnt > 0) 스택에 저장되어 있는 원소가 있는 경우 스택의 끝 수와 i번째 수를 비교하여 i번째 수보다 작은 스택의 끝 수를 제거하고 숫자 제거 횟수를 갱신시킴 결과를 출력할 때에는 스택에 담겨있는 수를 전체 자릿수에서 제거할 횟수를 뺀 만큼 순서대로 출력 💻 소스코드 import sys input = sys.stdin.rea..

[Python] BOJ / 3109번 / 빵집

3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 📝 풀이 그래프 탐색을 통해 가스관과 빵집을 연결하는 파이프라인의 최댓값을 구하는 문제 가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 함. 각 칸은 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선으로 연결할 수 있음 (-1, 1), (0, 1), (1, 1) 연결하는 파이프라인은 서로 겹칠 수 없음 visited 배열을 통해 구현 x축이 (c - 1)열에 도착했다는 것은 파이프라인이 성공적으로 연결되었다는 뜻 💻 소스 코드 impo..

[Python] BOJ / 1700번 / 멀티탭 스케줄링

1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 문제 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다. 예를 들어 3..