땀두 블로그

배열 하나를 만들어서, lost 배열에 인덱스 값은 1씩 빼주고, reserve 배열에 인덱스 값들은 1씩 더해준다. 이 기초 배열을 토대로 반복실행하여 해당 인덱스가 체육복이 없는 상황이면 인덱스가 마지막 학생이 아닌 경우, 뒤에 학생의 옷이 두 벌일 때 빌리고, 첫번째 학생이 아닌 경우, 앞에 학생이 옷이 두 벌일 때 빌리는 방식으로 답을 구해가면 된다. class Solution { public int solution(int n, int[] lost, int[] reserve) { int answer = 0; int [] ary = new int [n]; for(int i=0;i

그리디 알고리즘 중 거스름돈 알고리즘을 이용한 간단한 문제이다. 가장 큰 금액부터 비교해가며 금액을 제외하고, 그 카운트를 출력해주어서 해결하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p11047 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..

그리디 알고리즘을 이용하여 푸는 문제이다. 첫번째로 만난 행렬값이 다른 인덱스에서 부터 3*#크기의 값을 모두 바꾸어 주는 식으로 진행하면 된다. 처음에는 N*M에서 3보다 작은 부분이 남으면 그 부분만 바꾸어주어도 되는 줄 알아서 오답을 제출했는데 추후에 수정하여 맞았다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p1080 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub B..

이 문제는 아이디어가 떠오르지 않아 다른 블로그들의 답을 보고 문제를 풀었다. 그리디 알고리즘은 구현 자체는 어렵지 않았지만 아이디어를 캐치하는게 어려운 것 같다. 이 문제에서 주의할 점은 + 기호로 split할 때 \\+를 이용해야 한다는점 이외에는 크게 어렵지 않게 구현할 수 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class p1541 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new Buff..

탐욕법의 가장 대표적인 알고리즘으로 문제에 필요한 금액이 입력되면 가지고 있는 동전의 조합으로 해결하는 문제이다. 주어진 숫자 N을 충족하기 위해 동전의 배열에서 가장 큰 값부터 조건에 만족하면 추가하는 식으로 문제를 해결한다. public class coinChange { public static void main(String[] args) { // TODO Auto-generated method stub int N = 164; int ary[] = { 1, 5, 10, 50 }; int cnt = 0; for (int i = ary.length - 1; i >= 0; i--) { while (N > 0) { if (N >= ary[i]) { N -= ary[i]; cnt++; } else { brea..