소소한필통

Problem https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net About Problem 가장 중요한 부분이 N장의 카드에서 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력을 해야한다. 세장의 카드 밖에 없으므로 input에 범위에 따라서 어떤 알고리즘을 쓸지 결정한다 Input N이 100이므로 최대로 했을 때 100 * 99 * 98 이므로 10만정도 된다. 그러므로 dfs, 브루투포스 알고..

Problem https://programmers.co.kr/learn/courses/30/lessons/92342 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr About Problem 1. 과녁은 0 ~ 10점까지 총 11개의 종류로 구분된다 2. k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다. 3. a = b = 0 인 경우, 즉, 라이언과 어피치 모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도 k..

문제 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net About Problem 이 문제는 학생수와 비교 횟수를 주면서, 비교할 수 있는 사람 번호를 주기 때문에 간선 아래와 같이 간선 번호로 나타 낼 수 있다. 여기서 출려을 자신의 키가 몇 번째 인지 알 수 있는 학생들을 모두 구하라고 했으니 모든 정점에서 다른 모든 정점까지 최단 경로를 구할 수 있는 알고리즘인 플로이드 와샬을 썼다. 플로이드 와샬은 O(N^3)이므로 입력 값을 고려해서 쓰는 ..

문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net About Problem 문제의 핵심은 저 두줄이다. 간선의 정보를 주고 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 구하는 것이다. 간선의 비용이 양수이며 다르고 최소 비용을 구하는 알고리즘은 다익스트라 알고리즘이다. 간선의 최단경로를 구하는 알고리즘은 다음과 같다 Code 코드 설명은 코드 주석으로 적었다. from sys import stdin..

문제 https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr Prolem About 핵심 키워드 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려 고 합니다. 위 문장으로 이뤄 봤을 때 가중치가 각각 다른 그래프 중 최단경로를 구해야 하므로 다익스트라 알고리즘을 써야한다. 아래의 그림으로 최단경로를 구하는 문제에서 어떤 알..