본문 바로가기

그리디6

[백준/C,C++] 2812번: 크게 만들기 www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 스택을 이용해 풀 수 있는 문제입니다. 219879가 입력되었고, 지워야 할 숫자가 3개라고 생각해봅시다. 먼저 첫 번째 자릿수인 2를 스택에 push 합니다. 이후부터 각 자릿수를 탐색하며 스택에 push 되어있는 숫자를 비교합니다. 만약 탐색 중인 자릿수의 숫자가 스택에 push 되어있는 숫자보다 크다면 스택의 숫자를 pop 해주며 k를 감소 시켜 줍니다. 즉 현재 지워야 할 숫자가 남아있고, 이전 자릿수들의 숫자가 현재 자릿수의 숫자보다 작다면 지워주는 것입니다. 219879의.. 2021. 4. 20.
[백준/C,C++] 5585번: 거스름돈 www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 풀이 그리디 알고리즘 문제 중에서 가장 기초적인 문제입니다. 현재 받을 수 있는 화폐의 종류 중 값이 큰 것부터 잔돈에서 빼주면 됩니다. #include using namespace std; int main(void) { int n; cin >> n; n = 1000 - n; int changes[6] = { 500, 100, 50, 10, 5, 1 }; int res = 0; for (i.. 2021. 4. 20.
[백준/C,C++] 13305번: 주유소 www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 주유소의 리터당 가격이 제일 싼 곳에서 더 싼 도시를 가기 전까지의 거리만큼 주유하면 되는 문제입니다. 적어도 더 싸게 주유가 가능한 2번째 도시를 가기 전까지는 첫 도시에서 리터당 가격 5를 주고 주유를 할 수밖에 없습니다. 두 번째 도시에서는 마지막 도시에 도착할 때까지 보다 싼 주유가 불가능하기에 거리 4를 이동하기 위해 필요한 모든 기름을 리터당 가격 2를 주고 주유를 해야 합니다. 5 x.. 2021. 3. 14.
[백준/C,C++] 1541번: 잃어버린 괄호 www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 괄호를 쳐서 해당 식의 값을 최솟값으로 만들기 위해선 덧셈끼리 묵어 가장 큰 수를 만든 뒤 빼야 합니다. 가령 100+200-300+400과 같은 식이 있다면 (100+200)-(300+400)으로 식을 고쳐주면 최솟값이 나오죠. 그런데 100+200-300+400-500+600+700-800+900과 같은 식이 있다면 100+200-(300+400)-(500+600+700)-(800+900)으로 식을 고.. 2021. 3. 14.

티스토리툴바