YANGORITHM

문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어 www.acmicpc.net 풀이 이분 그래프 설명: https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B..

문제 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 풀이 N자리 정수가 있을 때, N번째(1의 자리)에 올 수 있는 수는 0~9 이다. 이때 0부터 9까지 각각 N-1의 자리에 올 수 있는 수는 다르다. N=0 이면 N-1=0 이고, N=1 이면 N-1=(0, 1) ......., N=9 이면 N-1=..

문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 N자리 수의 마지막 자리, 즉 1의 자리에는 0부터 9까지 올 수 있다. 이때 0과 9를 제외한 1부터 8까지는 앞 자리에 각각 2개의 수가 올 수 있다. 예를 들어, ○ ○ ○ ◎ ● 의 5자리 수가 있고 ●가 1이면 ◎에는 0, 2 이렇게 두 개가 올 수 있다. 하지만 ●가 0이면 ◎에는 1만 올 수 있다. 마찬가지로 ●이 9여도 앞에 자리에는 8만 올 수 있다. D[N][L] = N자리에 오는 마지막 수 L 이라고 하면 다음과 같은 점화식을 만들 수 있다. D[N][L] = { D[N][L] =..

문제 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까..