그리디 알고리즘8 13305 : 주유소 (C++) 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 그리디 알고리즘으로 해결한 문제이다. 처음에 조금 헷갈려서 문제를 이해하고 푸는데 좀 시간이 걸렸다. 반성하자. #include #define ll long long int using namespace std; // 거리와 가격이 최대 1,000,000,000이하로 // 들어옴으로 int로는 계산이 불가능 하다. ll total = 0; ll mini = 1000000001; int main() { int N; cin >> N; ll distance.. 2021. 2. 19. 2810 : 컵홀더 (C++) 2810번: 컵홀더 첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다. www.acmicpc.net 그리디 알고리즘을 사용하여 푸는 문제 주의할 점은 컵 홀더를 세는 것이 아닌 사람을 세야하는 문제. 좌석이 S만 나올 때는 자신의 왼쪽에 있는 컵홀더만 사용하다가 LL좌석이 나온 후 부터는 자신의 오른쪽에 있는 컵홀더만 사용할 수 있음과 동시에 이후 LL좌석이 나오는 때는 한 사람은 컵홀더를 사용할 수 없게 된다. 이에 맞춰 코딩을 하였다. #include #include using namespace std; int main() { int N; cin >> N; string seat; cin >> seat; int count = 0; int check = 0;.. 2021. 1. 19. 4796 : 캠핑 (C++) 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 그리디 알고리즘을 이용하여 푸는 문제로 총 휴가일 수에서 캠핑장을 이용하는 일수와 연속해서 이용하지 못하는 일의 수를 빼면서 계산하면 된다. 총 휴가일 수에서 캠핑장을 연속으로 이용하는 날의 수를 빼고 그 다음 이용하지 못하는 날을 뺀다. 그 다음 결과값에 캠핑장을 이용한 날을 더하고 총 휴가일의 수가 캠핑장을 이용할 수 있는 일자 보다 작아지면 while문을 나와 총 휴가일의 수가 음수면 더하지 않고 음수가 아니면 결과값에 남은 일의 수를 더한다. #in.. 2021. 1. 19. [백준] 2217번 : 로프(JAVA) https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 알고리즘 분류 중 그리디 알고리즘의 카테고리에 포함되어 있는 문제이다. 주의점은 "모든 .. 2020. 2. 13. [백준] 11399번 : ATM(JAVA) https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 18단계 그리디 알고리즘의 카테고리에 포함되어 있는 문제이다. import java.util.Scanner; import java.util.Arrays; public class Question_11399 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int .. 2020. 2. 12. [백준] 1931번 : 회의실배정(JAVA) https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 18단계 그리디 알고리즘의 카테고리에 포함되어 있는 문제이다. import java.util.Scanner; import java.util.Arrays; public class Question_1931 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int number = sc.nextInt(); int[][] fromTo = new int[num.. 2020. 2. 12. [백준] 11047번 : 동전 0(JAVA) https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 18단계 그리디 알고리즘의 카테고리에 포함되어 있는 문제이다. import java.util.Scanner; public class Question_11047 { public static void main(String[] args) { Scanner sc = .. 2020. 2. 12. [백준] 5585번 : 거스름돈(JAVA) https://www.acmicpc.net/problem/5585 5585번: 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 알고리즘 분류 중 그리디 알고리즘의 카테고리에 포함되어 있는 문제이다. import.. 2020. 2. 12. 이전 1 다음
