Jun's Development Journey

문제 www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 풀이 전형적인 그리디 알고리즘 문제이다. 거스름돈 종류 중 가장 큰 종류부터 순서대로 지불한다면, 최소의 갯수로 만들 수 있다. import java.io.*; import java.util.*; public class Main { static int[] changes = {500,100,50,10,5,1}; static int change_num(int change) { int cn..

문제 www.acmicpc.net/problem/2720 2720번: 세탁소 사장 동혁 각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다. www.acmicpc.net 풀이 import java.io.*; import java.util.*; public class Main { static int T; static int[] cents; static int[] changes = {25,10,5,1}; static String get_change(int change) { String str = ""; for(int i=0;i

문제 www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 www.acmicpc.net 풀이 import java.io.*; import java.util.*; public class Main { static int N, R; static int[] reco; public static void main(String[] args) throws IOException { //선언 및 입력 BufferedReader br = new BufferedReader(new InputStreamReade..

문제 www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int N, result; static int[] heights; static Stack stack; public stati..

문제 www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 import java.io.*; import java.util.*; public class Main { static boolean is_palin(String str) { int len = str.length(); for(int i=0;i

문제 www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; import java.util.StringTokenizer; public class Main { static int N, M; static int[][] city; static int[] parent; static int[] trip; publ..

문제 www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; import java.util.StringTokenizer; public class Main { static int N, M; static int[][] city; static int[] parent;..

문제 www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 랜선 길이의 최대값이 2^31 -1 이기 때문에 길이를 1부터 최대 길이까지 범위로 찾는 방식으로 풀면 시간 초과가 나올 것이다. 그러므로 범위를 줄여나가며 풀어야겠다고 생각했다. 찾아볼 범위의 시작을 start = 1이라 하고 범위의 끝은 end라고 했다. end는 랜선길이중 최대값 일 것이다. 중간값을 mid이라 했다. mid로 k개의 랜선을 잘랐을 때 개수가 n개 이..