www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net vector ball에 ((크기,색),번호)를 한꺼번에 저장하고 정렬을 하여 크기 순으로 정렬한 뒤, int all_psum에 전체 누적합을 구하면서 vector color_psum(200001, 0)에 각각 컬러의 누적합을 구해가며 문제를 해결했다. 코드 #include #include #include using namespace std; int n; vector ball; //(..

www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 트리DP(트리에서 다이나믹 프로그래밍)을 통해 문제를 해결했으며 cache[노드 번호][우수마을인지 아닌지][이전마을이 우수마을인지 아닌지]를 통해 문제를 해결했다. 유의할 점은 here이 우수마을이 아닌데, 이전 마을도 우수마을이 아니었을 경우이다 이때 there한곳은 무조건 우수마을이어야 하는데 자동적으로 there이 우수마을인 경우가 최적이 되는 경우에는 상관없지만 그렇지 않다면 우수마을로 선택했..

www.acmicpc.net/problem/16681 16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net 집에서 각각 지점으로 올라가는 최단경로와, 학교에서 각각 지점으로 올라가는 최단경로를 다익스트라 알고리즘을 통해서 구하고, 이를 통해 등산할 때 가치가 최대가 되는 값을 구한다. 코드 #include #include #include #include #include using namespace std; int n, m, d, e; vector h; vector adj[100001]; //(비용, 지점) ..

www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net Solve(int before_select, int mo, int ja, string maked)함수(before_select:이전에 확인한 인덱스, mo:모음의 개수, ja:자음의 개수, maked:만들어지는 문자열)를 통해 문자열을 만들어 가며 길이가 L인 문자열이 만들어졌을 때 모음, 자음 조건을 만족했는지 확인하여 문제를 해결했다. 코드 #include #include #include #include usin..

www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문자열 S와 T의 길이가 같아질 때까지 문자열 T를 확인하며 T의 끝이 'A'라면 해당 문자를 지우고, 끝이 'B'라면 해당 문자를 지우고 문자열을 뒤집는다. 그리고 S와 T의 길이가 같아졌을 때 같은 문자열인지 판단한다. 코드 #include #include #include using namespace std; string S; string T; string::iterat..

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net cache[100][100001]에 어떤 인덱스에 어떤 무게일때 배낭에 넣을 수 있는 물건들의 가치의 최댓값 저장했다. 각 인덱스에서 해당 물건을 고를 때와 고르지 않을 때를 비교해서 문제를 풀었다. 코드 #include #include #include using namespace std; int n, k; vector item; //무게, 가치..