Hello World

백준 2293 : 동전 1 문제 링크 www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 내용 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. Idea 다이나믹 프로그래밍을 하여 코드를 구현한다. f(n) += f(n-coin) 임을 이..

백준 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는 ..

백준 5585 : 거스름돈 문제 링크 www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사� www.acmicpc.net 문제 내용 잔돈으로 500엔, 100엔, 10엔, 5엔, 1엔이 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 잡화점에서 물건을 사고 1000엔을 냈을 때 받을 잔돈의 개수를 구하는 프로그램을 작성하시오. 단, 지불한 돈은 1 이상 1000 미만의 정수이다. Idea 사용 알고리즘 : Greedy Algorithm ( 탐욕 알고리즘 ) 제일 ..

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