Hello World

백준 4796 : 캠핑 문제 링크 www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 문제 내용 등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다. 캠핑장은 연속하는 20일 중 10일 동안만 사용할 수 있습니다. 강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가 기간 동안 강산이는 캠핑장을 며칠 동안 사용할 수 있을까? 강산이는 조금 더 일반화해서 문제를 풀려고 한다. 캠핑장을 연속하는 P일 중, L일동..

백준 2217 : 로프 문제 링크 www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 내용 N(1 ≤ N ≤ 100,000) 개의 로프가 있다. 이 로프를 이용하여 이런저런 물체를 들어 올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 ..

백준 11399 : ATM 문제 링크: www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 내용: 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오. Idea: 최소 대기시간..

백준 11047 : 동전 0 문제 링크 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 문제 내용 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. (단, 동전은 1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 ..

탐욕 알고리즘 Greedy Algorithm 탐욕 알고리즘이란? 최적화 문제를 해결하는 알고리즘으로 근시안적인 방법이다. 그 순간이 최적이라고 생각되는 것을 선택해 나가는 방식이다. 각 결정은 지역(local)적으로는 최적이나, 전체(global)적으로 봤을 때 최적이라는 보장은 없다. 대표 문제 동전 문제 배낭 문제 활동 선택 문제(회의실 배정) ... 동전 문제 Q. 어떻게 거스름돈의 개수를 최소한으로 줄일 수 있을까? [접근방법] 그 당시 거슬러줄 수 있는 가장 큰 액수의 동전을 선택한다. coin = 0 이면 종료 coin > 0 이면, coin보다 작거나 같은 동전 중 가장 큰 동전(m)을 선택 coin = coin - m 1~3 반복 *그러나 이 방법은 모든 coin system에서 동작한다는..

백준 4228 : The Dragon of Loowater 문제 링크: https://www.acmicpc.net/problem/4228 4228번: The Dragon of Loowater The input contains several test cases. The first line of each test case contains two integers between 1 and 20000 inclusive, indicating the number n of heads that the dragon has, and the number m of knights in the kingdom. The next n lines each contain an www.acmicpc.net 문제 내용: (요약) 머리가 n개가..