![]()
문제 출저https://www.acmicpc.net/problem/13699 문제 풀이t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0)점화식이 다음과 같은 수열이 주어집니다. 이 수열에 n의 값을 구해야 합니다. 1차원 long 배열 dp를 생성하여 점화식을 저장합니다. 소스 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/*점화식https://www.acmicpc.net/problem/13699 */public class Main { static long dp[]; public static void main(String[..
![]()
문제 출저https://www.acmicpc.net/problem/6126 문제 풀이동전의 종류와 금액이 주어집니다. 주어진 동전으로 금액을 만들 경우의 수를 구해야 합니다. dp를 이용해 문제를 풀었습니다. int[] dp = new int[n+1] 로 선언하여 금액 만큼 길이를 만듭니다. for (int j = coin; j 점화식을 세워서 문제를 풀었습니다. 소스 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.security.InvalidKeyException;import java.util.StringTokenizer;/*Cow Cashhttps://..
![]()
문제 출저https://www.acmicpc.net/problem/29160 문제 풀이문제를 요약하면 매년 각 포지션 별로 가장 능력치가 좋은 선수들의 능력치가 1씩 떨어집니다. 능력치는 1이하로는 떨어지지 않습니다. k 년 후에 각 포지션을 모두 더한 총합을 구해야 합니다. 우선순위 큐로 문저를 풀었습니다.1부터 11까지 각 포지션 별로 능력치가 높은 순서로 우선순위 큐를 만들었습니다. 포지션 별로 선수들을 집어넣습니다. k번 각 포지션 별 능력 좋은 사람을 꺼내 1을 감소하고 다시 우선순위 큐에 집어넣습니다. 이러면 손쉽게 가장 능력치가 좋은 사람을 선택할 수 있습니다. k번 반복하고 각 포지션 별로 가장 높은 능력치의 총합을 구했습니다. 소스 코드import java.io.Buffere..
![]()
문제 출저https://www.acmicpc.net/problem/29792 문제 풀이n개의 캐릭터 중 m개를 선택하여 보스를 잡아서 메소의 최대값을 구해야 합니다. n개의 케릭터는 각각 데미지가 있습니다. m개를 선택할 때 대미지가 큰 순서대로 선택했습니다. PriorityQueue 사용 보스는 체력과 메소가 주어집니다.한 케릭터당 사냥 시간은 15분 입니다. 대미지는 1초당 대미지 입니다. 즉 900초의 시간이 주어집니다. 900초 길이를 가진 1차원 int 배열을 만들어 배낭 알고리즘으로 최댓값을 구하고 더합니다.이 떄 입력값의 범위가 크므로 long을 사용합니다. 배낭 알고리즘은 현재 보스를 선택했을 때랑 선택하지 않을 때를 비교하여 더 큰 값을 dp인 1차원 배열에 저장하여 최대값을 구하..
![]()
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.lang.reflect.Array;import java.util.Arrays;import java.util.PriorityQueue;import java.util.StringTokenizer;/*나는 기말고사형 인간이야https://www.acmicpc.net/problem/23254 */public class Main { static int n; // 시간 static int m; // 과목 static int[] basic; // 기본 점수 static PriorityQueue growths; // ..
![]()
문제 출저 문제 풀이손님들이 원하는 초밥이 있고 초밥들이 순서대로 제공합니다. 손님 번호가 빠른 손님부터 초밥을 먹습니다. 각 손님이 초밥을 몇 개 먹는지 구해야 합니다. 우선순위 큐로 문저를 풀었습니다. 우선순위 큐를 2개 사용했습니다. 첫 번째 우선순위 큐는 (초밥 번호, 손님 번호)로 이루어져 있습니다. 초밥 번호가 작은 순으로 나오면 초밥 번호가 같다면 손님 번호가 작은게 나옵니다.두 번째 우선순위 큐는 제공되는 초밥을 담은 것으로 작은 번호 먼저 나옵니다. 초밥을 제공하는 우선순위큐에서 꺼내서 제공합니다. 초밥 번호가 같으면 첫 번째 큐에서 꺼내고 손님 번호에 해당하는 배열에 +1을 합니다. 만약 제공하는 초밥이 첫 번째 우선순위큐의 초밥 보다 크다면 큐를 계속 큐를 비워냅니다. 소..
![]()
문제 출저https://www.acmicpc.net/problem/2073 문제 풀이파이프를 선택하여 길이 d인 파이프를 만들려 합니다. 파이프는 길이와 용량이 주어집니다. 전체 파이프의 용량은 가장 작은 용량이 됩니다. 이 때, 용량이 가장 클 때를 구해야 합니다. dp, 배낭 문제로 문제를 풀었습니다. 전체 용량이 가장 큰 경우를 구해야 합니다. 파이프(길이 : l, 용량 : c)전체 길이를 d로 봤을 때 각각의 파이프 경우마다 전체 길이 d부터 현재 탐색하는 파이프의 길이 l까지 탐색합니다. 이미 있는 파이프의 용량(dp[j-l])과 현재 탐색하는 중인 파이프의 용량(c)을 비교하여 더 작은 것을 선택합니다. 이것을 기존에 용량(dp[j])와 비교하여 더 큰 것을 dp[j]에 저장하여 정..
![]()
문제 출저https://www.acmicpc.net/problem/29704 문제 풀이배낭 문제로 풀었습니다. 벌금을 최소화하기 위해서는 벌금이 높은 문제들을 풀어야 합니다. 다음과 같은 점화식이 나옵니다. for (int i = t; i >= 0; i--) { if (i 소스코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*벼락치기https://www.acmicpc.net/problem/29704 */public class Main { static int n; static in..
![]()
문제 출저https://www.acmicpc.net/problem/15817 15817번: 배수 공사합친 파이프의 길이 x를 만들 수 있는 방법의 수를 출력한다. 방법의 수가 2,147,483,647를 넘는 경우는 없다.www.acmicpc.net 문제 풀이파이프 종류 수 N과 합친 파이프의 길이 x가 주어집니다. N 종류의 파이프의 길이는 L과 수량 C가 주어집니다. x를 만들 수 있는 경우의 수를 구해야 합니다. dp를 이용해 문제를 풀었습니다. 파이프 종류를 이용해 만들 수 있는 길이를 업데이트 합니다. 주의점x는 12이고 4의 파이프가 3개 있다고 가정합니다.그러면 dp[4] = 1, dp[8] = 1, dp[12] = 1 이 되어야 합니다. 제가 기존에 풀었던 방식은 현재 파이프의 길이의 d..
![]()
문제 출저https://www.acmicpc.net/problem/12919 12919번: A와 B 2수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈www.acmicpc.net 문제 풀이BFS를 통해 풀었습니다. 시작 문자열 s, 목표 문자열 t가 주어집니다. s에서 시작해 t로 도달 할 수 있는지 구해야 합니다. 2가지 동작을 하 수 있습니다. 뒤에 A를 붙이거나 뒤에 B를 붙이고 두집을 수 있습니다. 처음 문제를 풀 때 s부터 시작해 t로 탐색을 진행했습니다. 이 때, 시..
![]()
문제 출저 https://www.acmicpc.net/problem/6144 6144번: Charm Bracelet Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1
![]()
문제 출저 https://www.acmicpc.net/problem/18427 18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 문제 풀이 학생이 가진 블록을 하나만 사용할 수 있다. 같은 학생의 블록들을 중복 사용하지 않도록 주의해야 합니다. 그 외에는 높이 h 크기인 1차원 int 배열을 사용하여 메모리제이션을 사용해서 문제를 풀었습니다. int[] before = new int[h+1]; int[] after = new int[h+1]; 두 개의 1차원 int 배열을 ..
