본문 바로가기

그리디4

[이코테] 4일차 Greedy _ 만들 수 없는 금액, 볼링공 고르기 🏆Today Code Test [1] 만들 수 없는 금액 🔴 동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요 입력 조건 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주저집니다. (1 ≤ N ≤ 1,000) 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수 입니다. 출력 조건 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다. 🛠Problem Approach ✅ 할 수 있는 모든 조합을 구함 → 조합 안 수를 순서대로 체크함 → 체크 안되는 수 출.. 2022. 5. 9.
[이코테] 3일차 Greedy _ 문자열 뒤집기 [1]문자열 뒤집기 🟢 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있습니다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 합니다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것입니다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미합니다. 문자열 S가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력하세요. 입력 조건 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어집니다.S의 길이는 100만 보다 작습니다. 출력 조건 첫째 줄에 다솜이가 해야 하는 행동의 최소 횟수를 출력합니다. 🛠Problem Approach ✅ 최소 횟수 → 뭉텅이 개수가 적은 애를 뽑아야지 → 플립이 되는 횟수의 절반(양 끝에서 모두 바뀌므로)이 최소 .. 2022. 5. 7.
[이코테] 2일차 Greedy_1이 될 때까지, 모험가 길드, 곱하기 혹은 더하기 🏆Today Code Test [1] 1이 될 때까지🟢 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다. N에서 1을 뺀다. N을 K로 나눈다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는지 최소 횟수를 구하는 프로그램을 작성하시오. 입력 조건 첫째 줄에 N(2 ≤ N ≤100,000)과 K(2 ≤ K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 크거나 같다. 출력 조건 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다. 🛠Problem Approach .. 2022. 5. 6.
[이코테] 1일차 Greedy _ 큰 수의 법칙, 숫자 카드 게임 🏆Today Code Test [1] 큰 수의 법칙 🟢 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 추가하여 더해질 수 없는 것이 이 법칙의 특징이다. 배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오. 입력 조건 첫째 줄에 N(2≤ N ≤ 1,000), M(1≤ M ≤ 10,000), K(1≤ K ≤10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다. 입력.. 2022. 5. 4.

티스토리툴바