서울에서 경산까지(http://boj.kr/14863) 냅색문제처럼 경로 둘 중 하나를 골라서 쌓는다는 느낌으로 구하면 된다. 나는 D[i][j] = i번째 경로까지 j분 이하의 시간으로 얻을 수 있는 최대 모금액이라고 정하고 풀었다.그러면 식은,D[i][j] = max(D[i - 1][j - 도보로 걸리는 시간] + 도보로 모으는 모금액, D[i - 1][j - 자전거로 걸리는 시간] + 자전거로 모으는 모금액)이 된다.하지만 이런 식으로 하면 i - 1번째 경로까지를 j - 시간만에 갈 수 있는지를 따로 확인해야한다. 12345678910111213141516171819202122232425262728#include using namespace std; int tme[101][2], money[101..
문명 (http://boj.kr/14868) BFS로 지도를 채워가면서 유니온 파인드로 문명을 구별해가면 된다. 확장할 때, 인접한 곳이 이미 채워져 있다면 다른 문명인지 확인하고,안 채워져 있다면 문명을 확장하고 그 확장된 곳에 다른 문명이 인접해 있는지를 확인한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293#include using namespace std; int mp[2001][2001], pr[100001], rnk[1000..
물통 (http://boj.kr/14867) 물을 A에서 B로 옮기던지, B에서 A에서 옮기던지 상관 없이 옮긴 후의 상태는 4가지가 된다. 1. A가 비어있음2. A가 가득참3. B가 비어있음4. B가 가득참 그렇기 때문에 모든 경우를 확인해도 2A+2B가지의 경우밖에 없기 때문에 시간초과가 나지 않는다. 다른 방법은, A에서 B로 물을 옮기고, 그 후에 B에서 A로 물을 옮기는 것은 최단의 방법일 가능성이 없다.마찬가지로 B에서 A로 물을 옮긴 후 A에서 B로 물을 옮기는 것도 가능성이 없다.A에서 B로 물을 옮기는 것을 기준으로 하면, A가 비었다면 물을 채우고, B가 가득 찼다면 물을 버리고, 그렇지 않다면 물을 옮기는 식으로 찾아가면 빠르게 구할 수 있다. 123456789101112131415..
부분집합의 합 2 (http://boj.kr/1208) 부분집합의 합 문제는 \(N\)의 제한이 \(20\)이기 때문에 모든 부분집합을 구하는 \(2^N\)의 방법으로도 풀 수 있었다. 하지만 이 문제는 \(N\)의 제한이 \(40\)이기 때문에 같은 방법으로는 풀 수 없다. 풀이부터 말하자면,배열을 반으로 나눠서 \(A\)와 \(B\)라고 했을 때,\(A\)의 부분집합의 합이 \(S\)가 되는 경우 + \(A\)와 \(B\)의 부분집합의 합이 \(S\)가 되는 경우 + \(B\)의 부분집합의 합이 \(S\)가 되는 경우를 구해야 한다.앞의 경우와 뒤의 경우는 그냥 구하면 \(2\times 2^{\frac{N}{2}}\)만에 구할 수 있고,가운데의 경우를 구하기 위해서는 \(A\)와 \(B\)를 합쳐야 ..
로고 (http://boj.kr/3108) 완전 탐색 문제라는 걸 알고 봤는데도 뭘 기준으로 탐색을 해야하는지 찾기 힘들었다. 이 문제는 격자에서 구역을 나누는 것 처럼(Flood Fill) 교차되는 사각형끼리 이동하며 생기는 구역의 개수를 찾는 문제였다. 사각형이 교차하는지 판단하는 방법은 여러가지가 있겠지만,사각형이 겹치면서 하나가 다른 하나를 완전히 포함하지 않는지를 확인했다. Flood Fill이나 BFS를 배울 때 안전 영역같은 문제만 있는 건 아니라고 알려주기 좋은 문제같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include using namespace std; int ax[1001], ay..
준오는 최종인재야!!(http://boj.kr/14657) 대회 때는 문제 자체도 이해하기 힘들었는데, 지금 다시 보니 트리의 지름 문제와 매우 비슷했다. 처음에 설명하는 문제 풀이 시스템은 사실 트리의 설명이다. 그리고 트리에서 가장 긴 경로(트리의 지름)을 찾는 것이다. 트리의 지름 문제와 다른 점은, 이 문제에서는 지나는 노드의 개수를 최대로 하면서 가중치는 따로 계산해야 한다. 트리의 지름을 구할 때는 아무 점이나 잡고 그 점에서 가장 먼 점 u를 찾고, u에서 가장 먼 점 v를 찾으면 u에서 v로 가는 경로가 트리의 지름이다. 그렇게 구현하니 맞기는 했는데, 저게 되는 이유가 잘 이해되지 않아서 그냥 모든 노드에서 자신이 지름에 포함되는 경우를 보도록 다시 구현했다. n = 2인 경우도 잘 고려..