Algorithm14 [Algorithm] Greedy 30 (백준) - 에이젠 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 공략 10^5개의 숫자로 구성된다라는 말은 예제를 보면 10^5보다 큰 숫자가 있었기에 자리수가 10^5 자리까지 있다는 것을 알 수 있었습니다. 완전탐색으로는 역시 풀 수 없겠죠. 1. 숫자 안에 0 이 꼭 필요하다. 30의 배수이기 때문에 0이 없으면 안 되는 것을 알 수 있었습니다. 1의자리 빼고는 3의배수가 나오도록 가장 큰 수를 찾아야하는데... 결국 힌트를 찾아보았습니다. 2. 모든 자.. 2022. 9. 12. [Algorithm] Greedy 대회or인턴 (백준) - 에이젠 https://www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net 실수 남자1명 여자2명인데 반대로 읽음... 낙오자 계산할때 팀매칭된 그룹 수를 갱신해 주지 않아서 틀림. 공략 알고리즘 중급 1/3 의 그리디 연습 문제입니다. 남자가 인원수가 훨씬 많다는 가정하에 과정을 설명해보겠습니다. 1. 각각 주어진 남 여 인원수를 팀에 필요한 인원수로 나눕니다. M / 2 : 몫1 + 나머지1 , N / 1 : 몫2 + 나머지2 2. 각각 나눈 몫중에 작은 값이 인턴이 없을 때 나올 수 있는 팀 개수입니다. 남자가 훨씬 많으니 몫2가 .. 2022. 9. 11. [Algorithm] Greedy 동전0 (백준) - 에이젠 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 공략 백준 알고리즘 분류가 아닌 온라인 강의에 있는 문제를 따라가면서 풀기로 계획을 바꾸었습니다. 알고리즘 중급 1/3 의 그리디 첫번째 문제입니다. 그리디 알고리즘을 처음 소개한대로 이번 문제도 매 순간 최적의 값을 찾아 반복하면 되겠습니다. 목표한 K원만큼을 최소한의 동전으로 채우는 것이 목표입니다. 가치가 큰 동전을 최대한 많.. 2022. 9. 2. [Algorithm] Dijkstra 특정한 최단경로 (백준) - 에이젠 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 공략 이전에 풀었던 최소비용 구하기 문제와 같은 다익스트라 알고리즘 문제 입니다. 공략법은 거의 같습니다만 추가로 생각해야할 부분이 서로 다른 두 개의 노드( V1 , V2) 를 무조건 통과해야한다는 조건이 생겼다는 것이죠. 예전에 BFS문제를 풀면서 각 두 경로의 길이를 비교해서 풀었던 기억이 있었기에 V1 -> V2과 V2 -> V1 각각의 경로 길.. 2022. 8. 26. [Algorithm] Dijkstra 파티(파티) - 에이젠 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 처음 다익스트라 공략 방법을 그대로 사용. 다만 단방향의 Edge에서 왕복을 해야한다는 내용이 추가된 문제. 다익스트라 알고리즘을 두번 사용하여 왕복하는 시간을 알아내었음. import java.util.*; class Main { static Scanner sc = new Scanner(System.in); static class Edge { int to ; int.. 2022. 8. 24. [Algorithm] Dijkstra 최소비용 구하기 - 에이젠 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄.. 2022. 8. 23. [Algorithm] 6월 19일 알고리즘 연습 (백준) - 에이젠 백준 2745 진법 변환 - 성공 직접 실행해서 볼땐 에러가 없는데 이러한 런타임에러가 계속 발생하였다. 알고보니 클래스 이름을 Main으로 지어야하는 문제... 내풀이 class Main { public static StringBuilder sb = new StringBuilder(); //숫자. public static String N = ""; //진법 public static int B = 0; static Scanner sc = new Scanner(System.in); public static void main(String[] args){ input(); System.out.println(converter()); } public static void input(){ N = sc.next(); .. 2022. 6. 19. 이전 1 2 다음 728x90
