코딩은 마라톤

[Silver IV] 설탕 배달 - 2839 문제 링크 성능 요약 메모리: 18804 KB, 시간: 236 ms 분류 다이나믹 프로그래밍, 그리디 알고리즘, 수학 문제 설명 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 ..

[Silver III] 등수 매기기 - 2012 문제 링크 성능 요약 메모리: 57256 KB, 시간: 872 ms 분류 그리디 알고리즘, 정렬 문제 설명 2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다. KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다. 자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 ..

[Silver V] 뒤집기 - 1439 문제 링크 성능 요약 메모리: 14284 KB, 시간: 124 ms 분류 그리디 알고리즘, 문자열 문제 설명 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1..

[Silver IV] ATM - 11399 문제 링크 성능 요약 메모리: 21560 KB, 시간: 308 ms 분류 그리디 알고리즘, 정렬 문제 설명 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에,..

1. 탐욕 알고리즘 Greedy algorithm이라고 부름 최적의 해에 가까운 값을 구할 때 사용한다. 여러 경우 중 하나를 결정할 때마다, 매순간 "최적"이라고 생각되는 경우를 선택해서 최종적인 값을 구한다. 2. 탐욕 알고리즘 예 문제 1: 동전 문제 - 지불해야 하는 값이 4720원일 때, 1원, 50원, 100원, 500원 동전으로 동전의 수가 가장 적게 지불하는 방식 1. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식 public class Main { public static void main(String[] args) { // 만약 동전 리스트가 내림차순으로 정렬되지 않을 경우 // 정렬을 해주어야 한다. sort int[] list = {500, 100, 50, 1}; Syst..