문제 14916번: 거스름돈N원을 최소 개수의 5원과 2원으로 거슬러 주는 프로그램을 작성하시오.www.acmicpc.net"> 14916번: 거스름돈N원을 최소 개수의 5원과 2원으로 거슬러 주는 프로그램을 작성하시오.www.acmicpc.net 접근법첫 접근 (잘못된 접근)처음 접근을 n이 홀수일 때와 짝수일 때를 나눠서 했다.n이 짝수일때는 5를 최대로 나눠도 나눈 나머지가 2로 항상 나누어 떨어지기 때문에 상관이 없다.하지만, n이 홀수일 때는 5로 나누는 순간 2로 나누어 떨어질수 없기 때문에, 5를 한번 덜 나누어 줬다. 무슨 말이냐면, 예를 들어 n=13일 때, 5로 나누게 되면 몫이 2이고, 나머지가 3이다. 3은 2로 나누어 떨어질 수 없기 때문에 5로 나눈 몫을 1로 바꾸고 나..

문제 1541번: 잃어버린 괄호덧셈과 뺄셈만으로 이루어진 수식에서 괄호를 적절히 배치해 결과를 최소로 만드는 프로그램을 작성하시오.www.acmicpc.net"> 1541번: 잃어버린 괄호덧셈과 뺄셈만으로 이루어진 수식에서 괄호를 적절히 배치해 결과를 최소로 만드는 프로그램을 작성하시오.www.acmicpc.net접근법예제 1부터 살펴보자55-50+40 ⇒ 55-(50+40) 로 계산해야 최적해가 나온다.그렇다면, -보다 +를 항상 먼저 계산하면 되는가?55+50-40 일때 + 를 먼저 계산한다고 해서 값이 작아지지 않는다.‘-’ 뒤에 나오는 수의 절댓값을 가장 최대로 만들어야 한다!!→ ‘-’ 뒤에 나오는 모든 ‘+’ 들을 먼저 연산한다.자료형은 어떻게 사용할까?숫자와 연산자를 따로 저장연산자..

문제 2217번: 로프N개의 로프를 이용해 들어올릴 수 있는 물체의 최대 중량을 구하는 프로그램을 작성하시오. 2217번: 로프N개의 로프를 이용해 들어올릴 수 있는 물체의 최대 중량을 구하는 프로그램을 작성하시오.접근법문제만 이해하면 쉬운 문제다.k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에 모두 고르게 w/k 만큼의 중량이 걸린다.N은 이미 입력값으로 주어지고 있기 때문에, 출력값이 W라고 하면 W/N 만큼의 중량이 각 로프에 골고루 걸린다.즉, N이 2이고, 10, 15가 로프의 가용중량으로 주어지면 2*10 = 20이 최대 중량이 되는 것이다.∵ W/N = (각 로프의 가용 중량 중 최솟값) / W = (각 로프의 가용 중량 중 최솟값) * N이때, 문제의 예외가..

문제 11399번: ATMN명의 사람이 줄을 서 있을 때 각 사람이 돈을 인출하는데 걸리는 시간의 합을 최소화하는 프로그램을 작성하시오.www.acmicpc.net"> 11399번: ATMN명의 사람이 줄을 서 있을 때 각 사람이 돈을 인출하는데 걸리는 시간의 합을 최소화하는 프로그램을 작성하시오.www.acmicpc.net접근법1. 계산법 자체가 뒤로 갈수록 숫자가 중첩되게 곱해지는 형태이기 때문에 정렬을 한 후 계산해야 한다.2. 현재 계산법은 모두 덧셈으로 이루어져 있는데 이를 곱셈으로 바꾸면 식이 훨씬 간단해진다.예) 1,2,3,4,5 현재 계산법 : 1 + (1+2) + (1+2+3) + (1+2+3+4) + (1+2+3+4+5)곱셈을 적용한 계산법 : 1*5 + 2*4 + 3*3 + ..

문제 1026번: 보물두 배열 A와 B가 있을 때, 배열 A의 재배열 순서를 결정하여 S의 최솟값을 구하는 프로그램을 작성하시오.www.acmicpc.net"> 1026번: 보물두 배열 A와 B가 있을 때, 배열 A의 재배열 순서를 결정하여 S의 최솟값을 구하는 프로그램을 작성하시오.www.acmicpc.net접근법곱셈은 곱해지는 두 수가 클수록 결괏값이 커지기 때문에 둘 중 하나의 값이 작아지면 결과가 확연히 작아진다.기본접근 ⇒ A를 정렬하고 B를 역정렬하여 같은 위치의 수를 곱해주고 그 결과의 합을 구한다. 하지만 이 문제는 단순정렬로도 해결할 수 있지만 그리디 알고리즘을 활용하면 더욱 효과적으로 해결이 가능하다.Queue구조의 pop을 활용한다고 생각하면 코드의 이해가 더 빠를 것이다. ..