Problem Solving/Greedy
백준 1789: 수들의 합 - 그리디
https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 1부터 +1씩 증가한 수를 원하는 수가 되거나 수를 넘게 될 때 까지 계속해서 더해줍니다. 만약 원하는 수가 되면 카운트 횟수를 그대로 출력하면 됩니다. ex) 원하는 수가 6일 경우 1 + 2 + 3 -> 3개 만약 원하는 수를 초과하게 될 경우 count에서 -1을 해준 값을 출력합니다. ex) 원하는 수가 4일 경우 1 + 2 + 3 = 6 6에서 2를 빼면 4, 결국 1+3한 경우이고, 답은 2 얼마만큼 초과를 했던지 그 수는 지금까지 더한 숫자 중 하나 일테고, 우린 그 값이 무엇인지 알아갈 필요가 없습니..
백준 1700: 멀티탭 스케줄링 - 그리디
https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 사용할 전기용품을 플러그에 꽂기 전에 세 가지 경우를 생각해야합니다. 이미 꽂혀 있는 경우 멀티탭에 빈 공간이 있는 경우 멀티탭에 있는 것을 뽑고, 새로운 것을 꽂아야 할 경우 1번의 경우 그냥 넘어가주면되고, 2번의 경우는 꽂고 넘어가주면 됩니다. 3번의 경우는 제일 마지막에 사용되거나, 앞으로 사용하는 일이 없는 것을 찾아 바꿔줍니다. 플러그에 꽂힌 전기용품을 기준으로 for문을 돌면서 현재 ..
백준 1439: 뒤집기 - Greedy
https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 처음에 stack에 1을 넣어주고, 문자열을 하나씩 보면서 값이 바뀌면 stack에 1을 추가합니다. ex) 001100111000 => [1, 1, 1, 1, 1] = [0그룹, 1그룹, 0그룹, 1그룹, 0그룹] 혹은 [1그룹, 0그룹, 1그룹, 0그룹, 1그룹] 값이 바뀌지 않았다면 모두 0이거나 1이기 때문에 뒤집어줄 필요가 없기 때문에 0을 출력합니다. 값이 바뀌었다면 stack 길이에서..
백준 - 1744: 수 묶기 - Greedy
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 세 가지 경우로 나누어 리스트에 저장을 했습니다. 1. 1을 제외한 양의 정수 2. 1 3. 0과 음의 정수 그런 후에 1번은 내림차순으로 정렬을 한 뒤 앞에서 부터 묶어주었고, 3번은 오름차순으로 정렬을 한 뒤 앞에서부터 묶어주었습니다. 2번은 1의 개수만큼 값을 더해주었습니다. 1번에서 1을 제외한 이유는 1은 곱하는 것보다 더해주는 것이 값을 더 증가시켜주기 때문입니다. 3번에서 0과 음의..
백준 - 2847: 게임을 만든 동준이 - Greedy
https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 뒤에서 부터 보면서 만약 다음 수가 현재 수보다 크다면, 현재 수보다 1 작은 값으로 만들어주면 됩니다. 1 작은 값으로 만들어야 점수를 낮추는 횟수를 최소화 할 수 있습니다. 문제 조건에서 항상 답이 존재하는 경우만 주어지기 때문에 1보다 작아지는 경우는 생각하지 않아도 됩니다. from sys import stdin input = stdin.readline n = int(input()) sc..