티스토리 뷰

문제 링크

 

A. Awkward Group

 

$N$개의 정점이 간선에 가중치가 있는 완전 그래프가 있다. 정점의 전체 집합 $P$의 부분 집합 $F$가 있다고 했을 때,문제에 적힌 조건을 만족하는 $F$의 개수를 구하는 문제다.

초기에 간선이 전혀 없는 그래프를 생각하자. 가중치가 작은 간선들부터 차례로 추가해나간다. 간선 하나를 추가할 때마다 그 간선이 속한 연결 요소(connected component)가 완전 그래프인지 확인한다. 만약 완전 그래프라면 그 연결 요소에 있는 정점들이 문제의 조건을 만족하는 집합 $F$가 됨이 자명하다. 완전 그래프인지 확인하는 것은 연결 요소 내의 정점 개수와 간선 개수를 비교하여 O(1)에 해결 가능하다. 만약 가중치가 같은 간선이 여러 개라면 한 번에 추가해야한다.

 

더보기

 

B. Card Game

 

점수가 적힌 $N$개의 카드가 일렬로 놓여있다. 한 턴에 가장 왼쪽 카드나 가장 오른쪽 카드를 가져갈 수 있다. 두 사람이 번갈아가면서 더 이상 가져갈 카드가 남아있지 않을 때까지 최선의 전략으로 게임에 임한다. 최종 점수는 자신이 가져간 카드에 적힌 점수의 합이다. 첫 턴을 진행한 사람이 얻는 점수를 구하는 문제다.

D[i][j] = i번째 카드부터 j번째 카드만 있다고 했을 때, 첫 턴을 시작하는 사람이 가져가는 점수 합의 최대값

위와 같이 DP 배열을 정의하자. 점화식은 아래와 같다.

D[i][j] = (i번째 카드부터 j번째 카드까지 적힌 점수 합) - min(D[i+1][j], D[i][j-1])

 

더보기

 

C. Consecutive Ordering

 

(문제 설명 생략)

각 구간에 대해서 자신과 교차하는 구간 번호 범위를 O(N)에 계산할 수 있다. i번 구간에 대해 교차하는 구간 번호 범위를 S[i] ~ E[i]라고 하자. 입력으로 주어진 새로운 순서에서 S[i] ~ E[i]가 연속하게 나오는지 모든 i에 대해 확인을 해주어야한다. 어떤 수 k(1 ≤ k ≤ N)가 입력으로 주어진 새로운 순서에서 몇 번째 순서인지 R[k]에 저장해두자. S[i] ~ E[i]가 새로운 순서에서 연속하게 나오는지 확인해주는 것은 S[i] ≤ j ≤ E[i]인 j에 대해 R[j]의 최대값과 최소값의 차이가 E[i] - S[i]인지 비교해주면 된다. 이는 Binary Indexed Tree나 Segment Tree, Interval Tree 등을 이용해서 시간복잡도 $O(N \lg N)$에 해결 가능하다.

 

더보기

 

D. Diameter

 

정점의 개수가 N개인 트리가 주어진다. 트리 간선의 가중치를 0까지 줄일 수 있고 가중치 1을 줄이는데 비용이 1만큼 든다. 이 때, 트리의 지름을 D이하로 만드는 최소 비용을 구하는 문제다.

차수가 2이상인 정점을 루트로한 Rooted Tree를 구성한다. 모든 정점에 대해 정점의 서브트리에서 그 정점을 지나는 경로의 길이가 D를 넘지 않으면 전체 트리의 지름 또한 D 보다 크지 않다. 이는 필요충분조건이다.

그러면 처음에 구성한 Rooted Tree에서 깊이가 낮은 순서대로 정점들을 처리하는데, 정점들을 처리할 때 그 정점의 서브트리에서 그 정점을 지나는 경로의 길이가 D이하가 되도록하는 최소 비용을 계산해주면 된다.

 

더보기

 

E. Grid Aliens

 

N*N 크기의 판의 각 점에 외계인이 살고 있다. 각 외계인은 W 혹은 Q 중 한 곳에 속해야 한다. i번 외계인은 값 h[i]를 가지고 있어, W에 속할 경우 h[i] 만큼의 점수를 얻고, Q에 속할 경우 1-h[i] 만큼의 점수를 얻는다. 그리고 서로 인접한 점에 있는 두 외계인이 서로 다른 곳에 속할 경우 점수는 1-|h[i]-h[j]| 만큼 감소한다. 이러한 상황에서 모든 외계인을 W와 Q 중 적절한 곳에 속하게 하여 전체 점수를 최대화 하는 문제다.

 

이 문제는 네트워크 플로로 해결할 수 있다. Google CodeJam 2015 Round 2의 C번 문제와 유사한 min-cut으로 해결한다.

max(CostW + CostQ - CostWQ)를 다시 쓰면 N- min(CostW` + CostQ` + CostW`Q`)로 쓸 수 있다. 여기서 W` = Q이고, Q` = W 이다.

아래와 같이 그래프를 구성하고 min-cut을 구하면 min(CostW` + CostQ` + CostW`Q`)을 구할 수 있다. 까닭은 코드잼의 C번 문제와 비슷하다. 

 

 

이와 비슷한 문제로는 2014년 전대프연 Bus Assignment 문제가 있다.

 

더보기

 

(추가) 위와 같은 그래프 디자인에서는 어떤 alien이 W와 Q 둘 다 들어가지 않는 경우를 min-cut으로 구하기도 한다. 따라서, 한 grid를 두 정점으로 분리하는 것이 아닌, 한 정점으로 유지하고 양방향 간선을 만들어준 뒤 min-cut을 구하면 올바른 답을 구한다. 반례가 되었던 입력 데이터는 코드에 주석으로 넣었다.

 

더보기

 

F. Merging Files

 

수열이 주어졌을 때, 인접한 두 수를 합칠 수 있다. 합치는 비용은 두 수의 합이고, 전체를 하나의 수로 합하는데 최소 비용을 구하는 문제다.

D[i][j] = i번째 수부터 j번째 수만 있다고 했을 때 하나의 수로 합치는 최소 비용

위와 같이 DP 배열을 정의하자. 점화식은 아래와 같다.

D[i][j] = (i번째 수부터 j번째 수의 합) + min(D[i][k] + D[k+1][j]) for i ≤ k < j

시간복잡도는 $O(N^3)$이다. Knuth Optimization을 통해 $O(N^2)$에도 해결가능하다.

 

더보기

 

G. Monotone Walkway

 

(0, 0)에서 시작하여 왼쪽으로 이동하지 않으며 방향을 90도씩만 꺽으며 이동하는 로봇이 방문한 점들이 주어진다. 불가능한 입력은 주어지지 않으며, 입력으로 주어진 점들의 순서를 찾아내는 문제다. 로봇이 방향을 꺽은 점은 항상 입력으로 주어진다.

x = a 꼴의 직선위에 있는 점들을 생각해보면 로봇이 이 직선을 위에서 아래로 이동했는지, 아래에서 위로 이동했는지 판단할 수 있다. 이를 판단하여 순서를 매겨주면 되는 쉬운 문제다.

 

더보기

 

H. Palindromic Numbers

 

입력으로 주어진 자연수 N에 대해 N을 B진법(2 ≤ B ≤ 64)로 나타냈을 때 회문이 되는지 판단하는 문제다.

2이상 64이하의 B에 대해 B진법으로 표현해보고 회문이 되는지 확인해주면 된다.

 

더보기

 

J. Pythagorean Expectation

 

야구에서 팀에 피타고라스 기대값을 정의할 수 있다. 시즌 시작부터 시즌 끝까지 야구 경기 기록이 주어지고, 시즌 내에서 팀들의 피타고라스 기대값을 계산하고, 최대값과 최소값을 구하는 문제다.

문제에서 하라는대로 하면 되는 간단한 문제다.

 

더보기

 

댓글
  • 프로필사진 명우짱 역시 갓명우 2015.10.06 20:45
  • 프로필사진 짱명우 역시 명우짱명우! 2015.10.07 10:39
  • 프로필사진 익명 비밀댓글입니다 2015.10.08 02:18
  • 프로필사진 전명우 포스트에 적혀 있는게 알고리즘 입니다만... 부족한 부분이 있나요? 2015.10.18 21:57 신고
  • 프로필사진 xhae 머싯엉 2015.10.12 11:01
  • 프로필사진 갓명우 d번 풀이는 없나요? 2015.10.17 20:18
  • 프로필사진 전명우 D번 생각한 풀이는 있는데, 검증이 안되서 나중에 하고 올리려합니다. 2015.10.18 21:58 신고
  • 프로필사진 익명 비밀댓글입니다 2015.10.22 18:11
  • 프로필사진 갓명우 갓명우! 2015.10.29 13:34
  • 프로필사진 hck F번 풀어보는 중인데 recursive가 아니라 동적 계획으로 풀려고 하거든욤
    ret = min(ret, dy(s, k) + dy(k+1, e) + S[e] - S[s-1]);
    이부분을
    sums[start][last] = min(sums[start][last], sums[start][m] + sums[m + 1][last] + lineSum[last] - lineSum[start-1]);
    이렇게 바꿨는데 답이 제대로 안나오네여 어떻게 바꿔야 할까여 ㅠㅠ
    2015.11.03 06:18
  • 프로필사진 명우짱 그거 루프를 잘 돌아야돼요
    대각선부터 채운다고 보면 쉬운데, 알고책같은데 있는 Chained Matrix Multiplication 문제나 Longest Palindromic Subsequence 문제 풀이법 보고 그대로 짜면 될거에요ㅎㅎ
    2015.11.08 10:07
  • 프로필사진 익명 비밀댓글입니다 2015.11.06 23:59
  • 프로필사진 전명우 답이 늦었네요. F번 문제 Knuth Optimization을 통해 O(N^2) 시간에 해결 가능합니다. 관련 포스팅을 참고해주세요. 2016.06.23 15:07 신고
  • 프로필사진 정봉수 혹시 이번부터 제가 경시대회 문제를 풀어볼려고 하는데 처음부터 할려니까 너무 막막한데 뭐 처음 공부하기 좋은거 참고해서 공부 할만한거 없을 까요? 2017.01.03 14:10
  • 프로필사진 전명우 구종만 저자의 http://book.algospot.com/ 책이 도움이 될 것 같네요.
    acmicpc.net에서 단계적으로 문제를 해결해서 경험을 키우는 것도 좋을 것 같습니다.
    2017.02.25 09:41 신고
  • 프로필사진 익명 비밀댓글입니다 2017.09.17 13:50
  • 프로필사진 전명우 문제가 전혀 기억 안 나는 상태에서 다시 읽어보았는데, 전체적으로 설명에 부족한 부분은 없는 것 같습니다. 특정 부분에 대한 추가 설명을 원하시면 어느 부분이 궁금한지 말씀해주세요. 2017.11.03 18:36 신고
  • 프로필사진 유명전짱 E번에서 bfs를 sink부터 시작하는 것 같은데, source부터 하지 않는 이유가 있을까요? 2021.01.07 01:26
  • 프로필사진 익명 비밀댓글입니다 2021.01.07 03:03
  • 프로필사진 전명우 댓글 확인이 매우 늦었네요. 네, 확인해보니 그래프 디자인에 문제가 있었습니다. 말씀해주신 것처럼 어떤 Alien이 W와 Q 둘 다에 속하지 않는 경우가 min-cut이 되는 경우가 존재합니다. 수정하겠습니다. 2022.07.10 12:21 신고
  • 프로필사진 knon0501 E번 설명대로 코드를 짜보고 채점해봤는데 모델링에 반례가 존재하는 것 같습니다.
    구사과님 코드(https://github.com/koosaga/olympiad/blob/master/ICPC/Korea/pre15_e.cpp)처럼 노드를 두 개로 분리하지 않아야 하는 것 같습니다.
    2022.07.04 04:27
  • 프로필사진 전명우 네, 확인하였습니다. 윗 분께서 말씀해주신 것처럼 원래 그래프 디자인에서는 어떤 alien이 W와 Q 모두에 들어가지 않는 경우를 min-cut으로 가져오는 문제가 있었습니다. 수정하겠습니다. 2022.07.10 12:22 신고
댓글쓰기 폼