문제 링크 www.acmicpc.net/problem/10021 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 풀이 기본적인 최소 스패닝 트리 문제입니다. 코스트가 $c$이상인 간선만 모아 최소 스패닝 트리를 만들어줍시다..
문제 링크 www.acmicpc.net/problem/1673 1673번: 치킨 쿠폰 강민이는 치킨 한 마리를 주문할 수 있는 치킨 쿠폰을 n장 가지고 있다. 이 치킨집에서는 치킨을 한 마리 주문할 때마다 도장을 하나씩 찍어 주는데, 도장을 k개 모으면 치킨 쿠폰 한 장으로 교환 www.acmicpc.net 풀이 초기 치킨 쿠폰이 $n$개, 그리고 도장을 $k$개 모으면 치킨 쿠폰이 하나 증가합니다. 1) 쿠폰 $n$개를 다 써서 만들 수 있는 새로운 쿠폰 수를 $c$라 합시다. $c = n / k$ (정수 나눗셈)입니다. 2) 갖고 있는 쿠폰을 $n*c$개만 썼다고 하고, 그렇게 만든 새로운 쿠폰을 $n$의 나머지에 더해줍니다. 3) 위 두 과정을 $n \geq k$인동안 계속 돌려줍니다. 4) 더 이..
문제 링크 www.acmicpc.net/problem/13544 13544번: 수열과 쿼리 3 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 풀이 예전에 Persistent Segment Tree 연습한다고 풀었던 문젠데, 이번엔 Merge Sort Tree를 연습한다고 풀어보게 되었습니다. 머지 소트 트리는 트리의 각 노드마다 항상 아래 두 노드의 리스트를 정렬된 상태로 갖고 있도록 저장하는 세그먼트 트리입니다. PST는 개념상 2차원 세그먼트 트리인데, 공간 효율을 높인 세그먼트 트리라고 보시면 됩니다..
문제 링크 www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 풀이 3대의 기관차가 항상 같은 수의 객차를 끌게 됩니다. 결국 N개중 3개의 시작점을 골라 최댓값을 뽑는 문제라고 생각할 수 있습니다. 기관차가 끌 수 있는 객차의 수만큼 구간을 잡고, 그 합을 미리 계산해두면 편하게 구현할 수 있습니다. 정답 코드 #include using namespace std; int d[55'555][3]; int n, k, p[55'555], sum[55'555];..
문제 링크 www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 풀이 일반적인 DP이지만 방향을 잘 잡아주어야 합니다. 저 같은 경우 어느 방향에서 왔는지에 대한 정보를 함께 넘겨주어, 그 방향으로는 다시 전개를 안 하게끔 구현했습니다. (line 20) 정답 코드 #include #define INF 0x3f3f3f3f using namespace std; int n, m, p[1111][1111]; int dx[] = {0, 1, 0}, dy[] = ..
문제 링크 www.acmicpc.net/problem/2281 2281번: 데스노트 첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m www.acmicpc.net 풀이 이름들을 순서대로 그룹 지어준다고 생각해봅시다. 각 그룹 값의 합의 상한은 노트의 폭과 같고, 그룹의 값은 (그룹에 포함된 이름의 길이 합 + [이름 개수] - 1)입니다. 간단한 DP로 풀 수 있습니다. $D[i]$: 그룹이 $i$번 이름으로 시작하고, 그 뒤의 모든 이름을 적절히 그룹으로 묶어주었을 때 남는 칸의 수의 제곱의 합의 최솟값 $[i], [i, i+..
문제 링크 www.acmicpc.net/problem/2306 2306번: 유전자 DNA 서열은 4개의 문자 {a,c,g,t} 로 이루어진 문자열이다. DNA 서열에는 생명의 신비를 풀 수 있는 많은 정보가 들어 있다. 특히 KOI 유전자의 길이는 사람의 키와 깊은 상관 관계가 있다는 것이 알려 www.acmicpc.net 풀이 DP 문제입니다. 상태를 다음과 같이 정의합시다. $D[i][j]$: 부분 문자열 $s[i, j]$의 최대 KOI 유전자 길이 1) 우선 간단하게 $i$이상 $j$미만의 모든 $k$에 대해, $$D[i][j] = \max_{k=i}^{j-1}(D[i][k] + D[k+1][j])$$ 이런 방식으로 i ~ j를 가능한 모든 두 구간으로 나누어보면 최댓값을 구할 수 있습니다. 2) ..
문제 링크 www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net 풀이 간단한 DP 문제입니다. 각 돌 그룹의 돌 개수를 상태로 하여 전개해줍시다. 주의할 점은 그룹당 가능한 돌의 개수가 1500개입니다. $O(1500^3)$으로 공간을 잡으면 메모리가 터지는데, 모든 돌의 개수는 항상 일정하다는 것을 생각하여 두 그룹의 돌 개수만 상태로 관리해도 괜찮습니다. 정답 코드 #include #define all(x) (x).begin(), (x).end() usin..
문제 링크 www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 풀이 구현 문제라 사실상 코드 설명이 되겠습니다. 1) 모든 공들을 크기순으로 정렬해줍니다. (코드상 $p$ 벡터) 2) 각 색별로 공들의 사이즈를 오름차순으로 저장해줍니다. (코드상 $cnt$ 벡터) 3) 모든 공을 순회하며, 자신보다 작은 사이즈 공 중(이전에 순회한 공들), 같은 색의 공을 제외한 나머지 사이즈합을 정답에 추가해줍시다. 정답 코드 #include #d..