문제 링크 : http://codeforces.com/problemset/problem/662/B N개의 정점과 M개의 엣지로 이루어진 그래프(N 빨강) 변하게 만들 수 있다. 이 때 최소 개수의 정점만 선택해서 모든 엣지의 색을 같게 만들 수 있는 방법을 구하는게 문제. 생각보다 단순한 방법으로 풀 수있는데, 일단 전체 엣지를 파랑으로 만들지 빨강으로 만들지 정해서 둘 중에 답이 더 작은 걸 답으로 고른다고 하자. 만약에, 그래프에서 임의의 정점 v1에 대해 그 정점 v1과 v2가 연결되어 있고 색깔은 빨강, 그리고 v1과 v3가 연결되어 있고 색깔은 파랑이라고 하자. 전체 그래프를 빨간색으로 바꾸려고 할 때, 만약 정점 v1을 선택한다면 v2는 반드시 선택해야만 하고, v1을 선택하지 않는다면 v2도..
링크 : http://codeforces.com/contest/876 5838점, 최종 순위 74위. 드디어 퍼플 복귀 가능할 듯! 간만에 잘쳐서 뿌듯한 대회였다. E번이 그리디하게 풀었는데 이게 답이 맞을 지 아닐 지 모르겠어서 시스템 테스트 끝날 때까지 전전긍긍하다가 결국 맞아서 너무 기분이 좋았다. A. Trip For Meal 그리디 문제인데, 문제를 제대로 안 읽고 빨리 풀어서 냈다가 한 번 틀려서 50점 감점 먹었다. 나는 일일히 모든 경우를 다 테스트하는 식으로 풀었는데 다른 사람 풀이를 보니 a,b,c 세 개중 어떤게 최솟값이냐에 따라 한 번에 계산할 수 있는 방법이 있었다. 얼핏 그런 방법이 있지 않을까 생각은 했었는데 어차피 A번이고 빨리 푸는게 장땡일 것 같아 처음 생각난 풀이 그냥 ..
링크 : https://www.acmicpc.net/problem/14454 어떤 문자열 S에 대해 그 문자열을 오른쪽으로 한 칸 민 문자열을 원래 문자열 S 뒤에 덧붙여 2배로 긴 새로운 문자열로 만드는 연산을 F라고 하자. 첫 문자열 S가 주어지고 여기에 F를 무한 반복해서 나오는 어떤 문자열이 있다고 했을 때, 그 문자열에서 n번째 위치에 어떤 문자가 들어갈 지를 구하는 문제다. 얼핏 생각하면 좀 까다로울 수 있는데, n번째 위치를 크게 나눠서 생각하면, 원래 문자열 s에 F를 쭉 반복해서 붙인 문자열 중 길이가 n보다 작으면서 가장 긴 걸 K라고 하자. 그러면 n번째 위치는 K를 오른쪽으로 한칸 민 문자열에서 n - (K의 길이) 위치에 있는 문자가 된다. 그러면 여기서 거꾸로 돌아가 n번째 위치..
링크 : https://www.acmicpc.net/problem/14777 그다지 어려운 문제가 아니었는데 문제 해석이 잘 안 돼서 한참 끙끙댔다. n개의 도시가 있고 첫 도시에서 시작해서 pi시간에 어떤 도시에 있을 수 있으면 그 도시에서 수여하는 상을 받을 수 있고, n개 도시 각각에 대해 움직이는데 걸리는 시간이 주어졌을 때 최대한 받을 수 있는 상 개수를 구하는게 문제다. 처음에 도시 개수 * 최대 시간 으로 모든 도시 왔다갔다하는거 다 계산하는 DP를 생각했는데 이러면 최대 시간 범위가 100만이라 시간 초과가 난다. 좀 더 생각하면 줄일 수 있는데, 각 도시에 대해 그냥 그 도시에서 수여하는 상 받을 지 아닐 지만 고민하면 되고, 이건 어떤 도시에 p[i]보다 일찍 도착한 다음 p[i]까지 ..
링크 : https://www.acmicpc.net/problem/5925 맨날 이런 문제 풀 때마다 헤매는데 또 헤맸다 ㅠㅠ 그리 어려운 문제가 아닌데 왜 맨날 이런 류 문제에서 헤매는지 모르겠다. 주어진 맵에서 3개의 상-하-좌-우로 연결된 조각이 주어지고 이 때 이 걸 1개짜리로 합칠건데 그럴려면 칸을 최소한 몇 개를 더 색칠해야하는 지 물어보는 문제이다. 처음에 BFS로 구현하려다가 이게 반례가 많다는걸 좀 헤매다가 깨닫고 구현을 바꿨다. 근데 그것도 잘 안 돼서 또 더 헤매다가 겨우겨우 품. 굳이 탐색을 안 해도 거리 계산 가능한데 대충 생각하고 탐색으로 구현하려고 한게 문제인 것 같다.