호두까기

문제 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로 바꾸고 나..

문제 2606번: 바이러스네트워크 상에서 컴퓨터 바이러스가 감염된 컴퓨터와 연결된 모든 컴퓨터를 감염시키는 과정을 시뮬레이션하는 프로그램을 작성하시오.www.acmicpc.net"> 2606번: 바이러스네트워크 상에서 컴퓨터 바이러스가 감염된 컴퓨터와 연결된 모든 컴퓨터를 감염시키는 과정을 시뮬레이션하는 프로그램을 작성하시오.www.acmicpc.net 접근법결국 그래프를 탐색하는 문제이기 때문에 DFS, BFS 둘중 하나를 선택해서 사용하면 되는 생각보다 쉬운 문제이다. 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Ma..

문제 13305번: 주유소도로와 주유소의 정보를 이용해 최소 비용으로 이동하는 방법을 구하는 프로그램을 작성하시오.www.acmicpc.net"> 13305번: 주유소도로와 주유소의 정보를 이용해 최소 비용으로 이동하는 방법을 구하는 프로그램을 작성하시오.www.acmicpc.net접근법리터당 가격이 가장 낮은 곳에서 최대한 많은 양의 기름을 채워야 한다.즉 리터당 기름 값이 ‘내림차순’일 경우에만 주유한다!!설명하기 쉽게 각 나라의 리터당 가격을 p라고 하겠다.순차적으로 왼쪽에서 오른쪽 나라로 이동한다고 한다고 가정하자.첫 나라에서 p를 읽어들이고 다음 나라로 순차적으로 이동 이동다음 p가 크거나 같으면 패스다음 p가 더 작다면 지금까지 온 모든 거리의 합에 가장 최근에 읽은 p를 곱한다.그렇..

문제 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이때, 문제의 예외가..