https://www.acmicpc.net/problem/1654 시간 제한메모리 제한제출정답맞힌 사람정답 비율2 초128 MB232219551953731121.425%문제집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)편의를 위해 랜선을 자르거나 만들 때 손실되..

https://www.acmicpc.net/problem/11663 시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초256 MB38811413105636.401%문제일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.출력입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출..

https://www.acmicpc.net/problem/11052 시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초256 MB52723324382451061.503%문제요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.전설카드레드카드오렌지카드퍼플카드블루카드청록카드그린카드그레이카드카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.민규는 카드의 개수가 적은 팩이더라도 가격..

https://www.acmicpc.net/problem/2294 시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초 (추가 시간 없음)128 MB75632233361661229.902%문제n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.입력첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.출력첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한..

https://www.acmicpc.net/problem/2293 시간 제한메모리 제한제출정답맞힌 사람정답 비율0.5 초 (추가 시간 없음)4 MB66085312772385947.364%문제n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.입력첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.출력첫째 줄에 경우의 수를 출력한다. 경우의 수는 231..

https://www.acmicpc.net/problem/1106 문제세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.각 도시에는 무한 명의 잠재..

https://www.acmicpc.net/problem/22869 사용 알고리즘DFS풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int n, k; static int[] jump1, jump2; static int min = Integer.MAX_VALUE; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inp..

https://www.acmicpc.net/problem/22869  사용 알고리즘다이나믹 프로그래밍 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;/* 테이블: d[j]: j번째 돌에 도달하는 최소 에너지 점화식: d[j]: Math.min(d[j], d[i] + energy) */public class Main2 { static int n, k; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReade..

https://www.acmicpc.net/problem/10844 사용 알고리즘다이나믹 프로그래밍 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/* 테이블: d[i][j]: 길이가 i이고 마지막 숫자가 j일때 가질 수 있는 모든 경우의 수 점화식: * d[i][j] = d[i-1][j-1] + d[i-1][j+1], 단 j-1>0, j+1  회고 이전에 못풀고 답안을 참고했던 문제인데 다시 풀어서 맞췄다! 테이블: d[i][j]: 길이가 i이고 마지막 숫자가 j일때 가질 수 있는 모든 경우의 수점화식: ..

https://www.acmicpc.net/problem/2156 사용 알고리즘다이나믹 프로그래밍 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/* 테이블: d[i]: i번째 포도주를 선택했을 때 최대값 점화식 * d[i] = d[i-2] + s[i] * d[i] = d[i-3] + s[i-1] + s[i] * d[i] = d[i-1] */public class Main { static int n; static int [] s = new int[10002]; sta..