알고리즘(w.KOTLIN)/그리디(Greedy) (16) 썸네일형 리스트형 [백준][코틀린][2109] 순회강연 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 문제 풀이 1. 입력으로 주어지는 강연 정보를 list 에 저장한다. 2. list 를 강연료를 기준으로 내림 차순 정렬한다. 3. 10001 크기의 lecture int 배열을 선언한다. 강연을 잡을 경우 lecture 배열에 강연료를 업데이트하는 용도로 사용한다. 4. list 를 다음과 같은 기준으로 탐색 한다. 4-1. list 의 d 값을 index 로.. [백준][코틀린][1202] 보석 도둑 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 문제 풀이 1. 보석의 정보를 jewel list 에 (무게, 가격)을 Pair 값으로 저장한다. 2. bag queue 에 가장 무게 정보를 저장한다. 3. jewel list 를 무게를 기준으로 오름 차순으로 정렬한다. 4. bag queue 를 오름 차순으로 정렬한다. 5. bag 의 queue 를 비어질 때 까지 pop 으로 꺼내.. [백준][코틀린][1285] 동전 뒤집기 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 문제 풀이 1. 주어진 동전들에 대해서 행/열을 각각 회전할 수 있다. 이때 행을 기준으로만 볼때 N=3 일 경우 다음과 같은 경우의 수로 행을 회전할 수 있다. - 행의 회전 경우의 수 1) 행을 회전하지 않는 경우 : 1가지 2) 하나의 행을 회전하는 경우 : (0행, 1행, 2행) : 3가지 3) 두 개의 행을 회전하는 경우 : (0, 1), (0, 2), (1, 2) : 3가지 4) 세.. [백준][코틀린][2138] 전구와 스위치 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 문제 풀이 1. 현재 전구 상태(currentLamp)와 만들고자 하는 상태(targetLamp) 를 선언한다. 2. lamp1Count, lamp2Count 를 선언하고 각각 스위치를 켠 횟수를 저장한다. 3. lamp1, lamp2 배열을 선언하고 lamp1에는 0번째 전구를 켜지 않은 배열을 저장하고 lamp2에는 0번째 전구를 배열을 저장한다. lamp2Co.. [백준][코틀린][1080] 행렬 https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 문제 풀이 1. 주어진 입력의 A 행렬을 matrix 에 B 행렬을 target 에 저장한다. 2. 이중 for 을 이용하여 matrix 행렬을 탐색한다. 3. matrix[i][j] != target[i][j] 인 경우 이면서 i + 2 1, 1 -> 0) 으로 바꾸고 바꾼 횟수를 count 에 저장한다. 4... [백준][코틀린][11399] ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 1. 시간 정보를 P 배열에 저장한다. 2. 배열 P를 오름 차순 정렬 한다. 3. 결과가 P[0] + (P[0] + P[1]) + (P[0] + P[1] + P[2]) ... 로 되므로 이중 for 문을 이용하여 결과를 구한다. 4. i 는 0부터 N까지 탐색하고 j는 0부터 i까지 탐색한다. 코드 import java.io.* fun main(args: Array) { val br = BufferedReader(.. [백준][코틀린][1931] 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 풀이 1. 주어지는 입력을 회의 (시작 시간, 종료 시간)을 저장하는 List 를 선언한다. 2. 1번에서 저장된 List 를 종료 시간을 기준으로 오름 차순 정렬 한다. 종료 시간이 같을 경우 시작 시간을 기준으로 오름 차순으로 정렬한다. 3. 결과를 출력하는 result 와 기준이 되는 시간을 저장하는 time 을 선언한다. 4. List 의 크기만큼 For 문을 돌려서 다음의 조건을 확인 한다. 5. list item 의 시작 시간이 time 보다 큰지 확인 한다. 6. 5번 조건에 해당될 경우 tim.. [백준][코틀린][11047] 동전 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. 주어진 조건의 입력 값을 저장하는 크기가 11인 배열 A를 선언한다. 2. i = N 부터 1까지 아래의 조건에 따라 탐색 한다. 2-1. A[i] > K 이면 동전의 가치가 목표하는 값보다 크므로 다음 탐색을 한다. 2-2. A[i] = K 이면 목표하는 값에 도달했으므로 결과를 출력한다. 이때 동전을 사용했으므로 .. 이전 1 2 다음
