SY DevLog

2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 다이나믹 프로그래밍과 위상정렬을 이용하여 푸는 문제 먼저, 위상정렬을 이용하여 작업간의 순서를 빠른 순서대로 큐에 저장해둔다. Queue order = new LinkedList(); 그리고 dp 일차원 배열에는 작업의 최소 완료시간을 저장한다. dp[n] : 작업 n을 완료하기 위해 필요한 최소 시간 큐에서 가장 먼저 실행되는 작업(n)부터 하나씩 꺼낸다. dp[n] = dp[n] + time[n] 으로, dp[n]에 해당 작업의 소요시간(time[n..

2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 이중 반복문을 사용해서 브루트포스 방법으로 해결하였다. 소스코드 :

2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 다이나믹 프로그래밍을 이용하여 풀이하였다. dp 배열을 3차원 배열로 만들었다. int[][][] dp = new int[T+1][3][W+1] int[][][] dp = new int[자두가 몇번째 떨어지는가][자두(사람이름)이 어느 위치에 있냐][이동횟수] dp[t][1][w] : t번째 자두가 떨어질 때, 1번 나무에서 떨어지는 경우 여태껏 w만큼 이동했을 때의 얻을 수 있는 자두 최대값 dp[t][2][w] : t번째 자두가 떨어질 때, 2번 나무에서 떨어지는 경..

백준 1655번 : 가운데를 말해요 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 최소힙(minHeap)과 최대힙(maxHeap) 두 개를 사용하여 푸는 문제였다. - 두 힙의 크기가 같으면, 최대힙에 입력한 값을 넣는다. - 두 힙의 크기가 다르면, 최소힙에 입력한 값을 넣는다. 그리고 최소힙의 peek() 과 최대힙의 peek()을 비교한다. 최소힙의 peek()가 최대힙의 peek()보다 더 작다면, 각각의 힙에서 poll()을 한 다음 서로 교환한다. 소스코드 :

백준 2169번 : 로봇 조종하기 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 다이나믹 프로그래밍을 이용하여 풀이하였다. 오른쪽, 아래쪽으로만 움직일 수 있었다면 문제가 쉬었을텐데, 왼쪽이동이 가능함에 따라 난이도가 올라갔다. 처음에 이중for문을 사용하여 현재 위치에서의 최대가치는 dp[i][j] 는 dp[i][j] = Math.max(dp[i][j-1], Math.max(dp[i-1][j], dp[i][j+1]) + w[i][j] 왼쪽에서의 최대가치(dp[i][j-1]), 위쪽에서의 최대가치(..

백준 15990번 : 1, 2, 3 더하기 5 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 정수 n을 1,2,3의 합으로 나타내되, 1,2,3 이 연속으로 더해져서는 안된다. 백준 9095번 : 1,2,3, 더하기 문제에서 약간 변형하여 다이나믹 프로그래밍으로 해결하였다. 기존에 9095번 문제에서 dp 점화식은 다음과 같았다. dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 그런데 이번 문제에서는 같은 수가 연속으로 나오면 안되므로 dp를 이차원 배열로 만들어서 dp[n] 를 연산의 마지막이 1로 끝나는지, 2로 끝나는지, 3으로 끝나는지에..

백준 9095번 : 1, 2, 3 더하기 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍을 이용하여 풀 수 있다. dp 1차원 배열을 생성하고, dp[n] 는 정수 n을 1,2,3 의 합으로 나타낼 수 있는 경우의 수를 의미한다. dp[1] 은 1로만 나타낼 수 있으므로 1가지이다. n = 1 일 때, 1 한 가지이므로 dp[1] = 1 이다. n = 2 일 때, 1 + 1 2 두 가지이므로 dp[2] = 2 이다. n = 3 일 때, 1 + 1 + 1 2 + 1 1 + 2 3 총 4가지이므로 dp[3] = 4 이다. n = 4 일 때, 1 + 1 + 1 +1 2 + 1 + 1..

백준 16194번 : 카드 구매하기 2 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 다이나믹 프로그래밍으로 풀었다. dp 1차원 배열을 만들고 dp[N]는 무게 N일 때의 최소 비용을 담는다. dp[N]는 dp[0] + dp[N], dp[1] + dp[N-1] : 무게1 일 때의 최소비용 + 무게 N-1 일 때의 최소비용 dp[2] + dp[N-2] ... dp[N/2] + dp[N/2] 중에서 최소가 되는 비용을 담는다. 소스코드 :

백준 9184번 : 신나는 함수 실행 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 다이나믹 프로그래밍으로 풀었다. 처음에 단순히 삼중 for문을 사용하여 풀었는데 결과가 '틀렸습니다' 가 떴다. import java.io.*; public class Main { static int[][][] dp = new int[51][51][51]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(..

백준 1969번 : DNA 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 구해야 하는 DNA를 S라고 하면, S의 0번째 문자부터 M-1번째 문자를 정해야 한다. N개의 DNA의 k번째 문자들 중 가장 많이 등장한 문자가 S의 k번째 문자가 된다. 예를 들어, TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 와 같이 5개의 DNA가 있다고 하자. TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 5개의..