mojo's Blog

문제 링크 => 19539번: 사과나무 (acmicpc.net) 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 그리디 알고리즘 문제이다. 1과 2를 동시에 사용하여 나열된 나무의 높이를 만들어 내도록 하는 문제이다. 이때 다음과 같은 예는 성립하지 않는다. [1 1 2 2 2] => 마지막에 2만 남으므로 성립하지 않음 [1 1 1 2 2 2 2] => 이 또한 마지막에 2만 남으므로 성립하지 않음 즉, 합이 3의배수가 아닌 경우는 무조건 "NO" 이다. 그리고 합이 3의 배수일때의 예를 살펴보도록 한다. [1 1 2 2] => 1, 2를 모두 사용하여..

문제 링크 => 10090번: Counting Inversions (acmicpc.net) 10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net A permutation of integers from 1 to n is a sequ..

문제 링크 => 2662번: 기업투자 (acmicpc.net) 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 투자액이 정해져 있고, 기업의 개수와 각 기업에 투자했을 경우에 얻게 되는 이익이 주어졌을 때 가장 많은 이익을 얻을 수 있는 투자방식과 이때의 이익금을 구해야 한다. 이때, 이차원 배열 arr, memo, invest, visited 에 대해서 설명하자면 다음과 같다. arr[x][y] => 기업 y에 금액 x 만원을 투자하는 경우 얻게 되는 이익 memo[x][y] => 기업..

문제 링크 => 2533번: 사회망 서비스(SNS) (acmicpc.net) 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 얼리 아답터인 경우와 얼리 아답터가 아닌 경우를 나누기 위해 2차원 배열 memo[1000001][2] 를 설정하였다. 얼리 아답터인 경우 (memo[x][1]) => memo[x][1] += min(dp(next, 1, x) + 1, dp(next, 0, x)) (그 다음 노드가 얼리 아답터인 경우와 얼리 아답터가 아닌 ..

문제 링크 => 2248번: 이진수 찾기 (acmicpc.net) 2248번: 이진수 찾기 N(1 ≤ N ≤ 31)자리의 이진수가 있다. 이러한 이진수 중에서, L(1 ≤ L ≤ N)개 이하의 비트만 1인 것을 크기 순으로 나열했을 때, I번째로 나오는 이진수를 구해내는 프로그램을 작성하시오. 이진수 www.acmicpc.net 다이나믹 프로그래밍 문제이다. N(1 ≤ N ≤ 31)자리의 이진수가 있다. 이러한 이진수 중에서, L(1 ≤ L ≤ N)개 이하의 비트만 1인 것을 크기 순으로 나열했을 때, I번째로 나오는 이진수를 구해내는 프로그램을 작성하시오. 이진수는 0으로 시작할 수도 있다. 2차원 배열 memo[x][y] 를 설정했을때 x는 자릿수를 결정하도록 하고 y는 해당 자릿수 x에서 비트 1를..

문제 링크 => 13398번: 연속합 2 (acmicpc.net) 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 수는 한개 이상 선택해야 하고, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다) 이때 수를 제거하지 않고 얻어낼 수 있는 최댓값과 수열에서 수를 하나 제거하여 얻을 수 있는 최댓값 두가지로 분류하여 구해내야 한다. ..