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

문제 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을 활용한다고 생각하면 코드의 이해가 더 빠를 것이다. ..

문제 1018번: 체스판 다시 칠하기N×M 크기의 보드에서 8×8 크기의 체스판으로 잘라낼 때 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.www.acmicpc.net"> 1018번: 체스판 다시 칠하기N×M 크기의 보드에서 8×8 크기의 체스판으로 잘라낼 때 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.www.acmicpc.net접근법이 문제의 핵심은 총 2가지이다.1. 기본적으로, 브루트포스 알고리즘이기 때문에 처음부터 끝까지 모두 탐색할 생각으로 접근해야 한다.2. 8x8 정사각형의 첫 번째 block은 검은색일 수도 하얀색일 수도 있다.3. 전체 보드가 NxM 크기라고 할때, 그곳에 들어가는 체스판의 개수는 (N-7) x(M-7)이다. -..

문제 1181번: 단어 정렬알파벳 소문자로 이루어진 N개의 단어가 주어지면, 아래의 조건에 따라 정렬하는 프로그램을 작성하시오.www.acmicpc.net"> 1181번: 단어 정렬알파벳 소문자로 이루어진 N개의 단어가 주어지면, 아래의 조건에 따라 정렬하는 프로그램을 작성하시오.www.acmicpc.net솔루션import java.io.*;import java.util.*;public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWri..