Uknow's Lab.
article thumbnail
[백준 11047번] [Kotlin] 동전 0
코딩테스트/Kotlin 2023. 3. 29. 21:09

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 난이도 : 실버 4 태그 : 그리디 설명 그리디 알고리즘 문제로, 늘 최적의 해를 선택하는 문제입니다. 동전의 개수를 최소로 해야 하므로, 동전의 단위가 가장 큰 것부터 선택해야 합니다. 소스코드 import java.io.BufferedReader import java.io.InputStreamReader fun main() { v..

article thumbnail
[백준 13305번] [Kotlin] 주유소
코딩테스트/Kotlin 2023. 3. 26. 21:58

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 난이도 : 실버 3 태그 : 그리디 설명 그리디 알고리즘을 통해 풀 수 있는 문제입니다. 현재의 주유소보다 다음 주유소가 더 효율이 좋다면, 무조건 다음 주유소로 이동하는게 효율적입니다. 따라서, 현재 주유소보다 효율이 좋은 주유소를 탐색한 후, 해당 주유소까지 이동할 기름만 충전한 후, 해당 주유소르 이동합니다. 소스코드 import java.util.* fun main() = w..

article thumbnail
[백준 5585번] [Kotlin] 거스름돈
코딩테스트/Kotlin 2023. 2. 4. 19:18

https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 난이도 : 브론즈 2 태그 : 그리디 설명 500엔, 100엔, 50엔, 10엔, 5엔, 1엔으로 잔돈을 거스름돈 하는 문제입니다. 전형적인 그리디 알고리즘 문제인데요. 가장 최적의 해를 연속하여 선택하는 방법입니다. 이 문제에서는 거스름돈의 개수가 가장 적어야 하므로, 단위가 가장 큰 500엔부터, 100, 50, 10, 5, 1엔 순으로 선택하면 되겠네요. 소스코드 fun..

article thumbnail
[백준 2217번] [Kotlin] 로프
코딩테스트/Kotlin 2023. 2. 4. 19:07

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 난이도 : 실버 4 태그 : 수학, 그리디, 정렬 설명 n개의 로프가 주어지고, k개의 로프로 w만큼의 물체를 들어올릴때, 각 로프에는 w/k의 부하가 걸립니다. 10를 버틸 수 있는 로프 하나, 15를 버틸 수 있는 로프 하나가 있으면 15개 하나를 사용하는 것 보다는, 10만큼씩 2개를 사용해 20의 무게를 들어올리는게 더 효율적입니다. 각각 5, 10, 15, 20, 25를 들어올릴..

article thumbnail
[백준 2109번] [Kotlin] 순회강연
코딩테스트/Kotlin 2023. 1. 24. 00:52

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 난이도 : 골드 3 태그 : 자료구조, 그리디 알고리즘, 우선순위 큐, 정렬 설명 d일 안에 강의를 하러 오면 p만큼의 돈을 받을 수 있습니다. n개의 강의를 갈 수 있을 때, 최대로 벌 수 있는 돈을 구하는 문제입니다. 이 문제를 처음 봤을 때 든 생각은, 아! 일자를 오름차순 정렬하고, 돈을 내림차순 정렬하면 되겠구나! 생각했습니다. 하지만, 머지않아 몇 개..

article thumbnail
[백준 1343번] [Kotlin] 폴리오미노
코딩테스트/Kotlin 2023. 1. 17. 21:47

https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 난이도 : 실버 5 태그 : 구현, 그리디 알고리즘 설명 XXXX를 AAAA를, XX를 BB로 바꾸는 그리디 알고리즘 문제입니다. replace로 AAAA를 먼저 바꾼 뒤, 그 다음 BB를 바꾸면 됩니다. 소스코드 fun main() { val line = readLine()!!.replace("XXXX", "AAAA").replace("XX", "BB") println(if (line.indexOf('X') == -1) line else -1) }

article thumbnail
[백준 11399번] [Kotlin] ATM
코딩테스트/Kotlin 2022. 12. 26. 13:57

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 난이도 : 실버 4 태그 : 그리디 알고리즘, 정렬 설명 각 사람이 돈을 인출하는데 걸리는 최소한의 시간을 찾는 문제입니다. 단순히, 각 사람의 인출시간을 오름차순으로 정렬하여 기다린 시간만큼 더해주면 됩니다. 소스코드 fun main() { val testCase = readLine()!!.toInt() val nums = readLine()!!.toString().trim().split(" ").map { i -> i.to..

article thumbnail
[백준 16953번] [Kotlin] A → B
코딩테스트/Kotlin 2022. 12. 12. 22:45

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A B 보단, B를 역으로 A로 만드는 과정이 더 쉬우며, 오른쪽에 1을 추가하는 연산은 10으로 나눴을때 나머지가 1이면 오른쪽에 1을 추가한 연산으로, 2..

article thumbnail
[백준 2057번] [Python] 팩토리얼 분해
코딩테스트/Python 2022. 11. 29. 10:36

https://www.acmicpc.net/problem/2057 2057번: 팩토리얼 분해 음 아닌 정수 N이 주어졌을 때, 이 수를 서로 다른 정수 M(M ≥ 1)개의 팩토리얼의 합으로 나타낼 수 있는지 알아내는 프로그램을 작성하시오. 예를 들어 2=0!+1!로 나타낼 수 있지만, 5는 이와 같은 www.acmicpc.net 난이도 : 실버 5 태그 : 수학, 그리디 알고리즘, 브루트포스 알고리즘 설명 정수 n이 주어졌을 때, 서로 다른 팩토리얼로 나타낼 수 있으면 YES, 아니면 NO를 출력하는 문제입니다. 정수 145이 있습니다. 145이하의 팩토리얼 중 가장 작은 팩토리얼은 5! (5*4*3*2 = 120)입니다. 4!을 볼까요? 4*3*2 = 24로, 120 + 24 = 144로, 145보다 ..

article thumbnail
[백준 1202번] [Kotlin] 보석 도둑
코딩테스트/Kotlin 2022. 11. 13. 17:37

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 난이도 : 골드 2 태그 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐 설명 정렬과 우선순위 큐를 사용해 풀 수 있습니다. 보석의 경우, 무게로 내림차순 정렬하고, 무게가 같을 경우 오름차순 정렬을 합니다. 가방도 무게를 기준으로 오름차순 정렬하고, 각 가방의 무게보다 가볍거나, 같은 보석의 가격을 우선순위 큐(내림차순)에 넣고,..