mojo's Blog

문제 링크 => 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를..

문제 링크 => Problem - B - Codeforces Problem - B - Codeforces codeforces.com 문자열 관련하여 '^' 연산자를 사용하는 문제이다. 아이디어는 다음과 같다. 기존 문자열의 쌍과 기존 문자열의 쌍에 대한 permutated 문자열의 쌍을 각각 '^' 연산을 취해주면 0이 된다. (이때 0을 베이스로 깔고 감) 즉, (2*n - 1) 개의 문자열 중에서 stolen string을 제외한 문자들을 전부 '^' 연산을 한 결과는 0이 됨을 아는것이 중요하다. 풀이 code #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #i..

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

문제 링크 => 11003번: 최솟값 찾기 (acmicpc.net) 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 우선순위 큐를 이용하는 문제이다. (덱을 활용해도 풀리는 문제) 앞과 뒷부분을 가르키도록 하는 변수 front, end를 선언하였다. 그리고 priority_queue pq 를 선언하여 첫번째에 배열값, 두번째에 인덱스값을 push하고 오름차순으로 정렬하도록 구현하였다. front ~ end 범위 내에 인덱스가 존재하는 경우 => 가장 작은 값이므로 출력한다. fr..