YANGORITHM

문제 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 1부터 N까지의 수 중에서 조합을 해서 N을 만드는 경우의 최대값을 구하는 문제이다. D[N]을 N개를 갖기 위해 지불하는 최대 금액으로 한다. N이 4라고 하고 P[1] ~ P[4]까지 카드의 금액이 주어진다고 하면 ○ + ○ + ○ + ● = 4 에서 ●에 올 수 있는 수는 1, 2, 3, 4 가 된다. 그럼 가능한 점화식은 다음이 된다. D[4] = max { D[4-1] +P[1], D..

문제 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 풀이 9개 중에서 7개를 골라서 더하여 100을 만드는 것보다, 9개의 합에서 2개씩 순서대로 묶어서 빼다가 100이 되는 순간 출력을 하면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #includ..

문제 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 풀이 점수가 최대가 되야하므로 점수를 내림차순으로 정렬해서 선택한다. 그리고 마감일이 오래 되는 과제는 당장 해결 할 필요가 없으므로 미룰 수 있을 만큼 미뤄야 한다. 이를 위해 배열 due를 만들어서 이 배열에다 선택 된 과제들만 저장한다. 1. index에 마감일을 저장 2. 마감일이 중복이 아니면 (due[index] == 0) 점수 저장 (마감일까지 과제를 최대한 미룸) 3. 마감일이 중복되면 (due[index] != 0) -..

문제 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 K; for (int i = 0; i > sensor[i]; sort(sensor, sensor + N); // 인접한 센서 사이의 거리 for (int i = 0; i

문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 부분수열은 연속적인 부분수열을 의미하는 것이 아니었다. 1, 2, 3, 4의 수열이 있으면 (1, 4), (1, 3, 4) 같이 떨어져 있어도 부분수열이 된다. 이것 때문에 헷갈린 문제다. 배열 각각의 원소를 포함하거나 포함하지 않거나의 2가지 경우로 배열의 모든 인덱스를 탐색하면 된다. 길이가 최대 20이므로 최대 2^20번의 경우가 나온다. 재귀 ..

문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 풀이 어떤 수를 제곱수들로 표현을 할 때 , 무조건 큰 수의 의 제곱수들로만 나타내는 것은 답이 아니다. 예를 들어 43 = 25..

문제 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. www.acmicpc.net 풀이 동전의 종류가 n개이고 구하고 싶은 가치가 k 일때 f(n, k)를 n번째 동전부터 사용하여 k를 나타내는 최소의 동전 수 로 한다. 이런 식으로 f(n+1, k)... 를 불러서 문제를 해결 할 수 있다. 동전의 수를 N 이라하고 각 동전의 가치를 coin[i]로 하면 면 다음과 같은 점화식을 구할 수 있다. 동전의 범위는 0부터 N-1까..

문제 https://www.acmicpc.net/problem/1935 1935번: 후위표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. (3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 정수이다) www.acmicpc.net 풀이 후위표기식으로 된 식을 계산하는 문제이다. 1. 피연산자를 만나면 스택에 push한다. 2. 연산자를 만나면 스택에 있는 두 ..

문제 https://www.acmicpc.net/problem/1918 1918번: 후위표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. www.acmicpc.net 풀이 중위 표기식을 후위 표기식으로 바꾸는 문제이다. 스택을 이용하는 대표적인 문제이다. 식에 존재하는 연산자는 + - * / 인데 * / 가 + - 보다 우선순위가 높다. 그리고 같은 우선순위라면 먼저 나오는게 더 우선순위가 높게 된다. 이 점을 이용하여 알..

문제 https://www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 문제 크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에다가 i부터 j까지의 최솟값을 곱한 것이 점수가 된다. 배열이 주어졌을 때, 최대의 점수를 갖는 부분배열을 골라내는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N이 주어진다. 다음 줄에는 A[1], …, A[N]을 나타내는 정수들 www.acmicpc.net 풀이 이유 : 가운데를 걸치는 부분배열에서 최대값을 구할 때 시간초과가 났다. 최대 부분 배열을 고르는 알고리즘은 분할 정복..