분류 전체보기
-
백준 10653(마라톤 2)전공/알고리즘 2020. 10. 2. 16:25
www.acmicpc.net/problem/10653 10653번: 마라톤 2 젖소 박승원이 2번째 와 4번째 체크포인트를 건너뛸경우 경로는 (0,0) -> (1,1) -> (2,2) 로 4가 된다. 이보다 더 짧게 달릴수는 없다. www.acmicpc.net 문제를 보자마자 재귀의 점화식이 떠오르긴 했다. 근데 이게 dp인지는 알기가 힘들었다. dp가 뭔지 제대로 모르고 있어서 그런가 그래도 점화식을 바탕으로 dp라고 생각하고 풀었다. 처음에는 최대 K개를 계속해서 패스할 수 있다는 건줄 알고 그렇게 풀었으나 틀렸습니다.를 맞은 후에 알았다. 재귀형식으로 돌아가는 구조와, 점화식 이 두개만 알면 구현도 쉬운 dp문제이다. dp[N][K]는 N체크포인트에서 K개의 건너 뜀을 행하였을때의 최소 값을 저장한..
-
백준 1939(중량제한)전공/알고리즘 2020. 9. 30. 13:59
www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net dfs와 bfs의 차이점과 특징을 상기시켜준 문제. 처음에는 그냥 dfs로 풀었다. 그러자 TLE 최악의 경우에 거의 N*M의 시간복잡도를 가지므로, 10^9 시간초과 발생가능성이 존재한다. 따라서 시간을 더 줄일 방법을 찾아야 했다. 단순 탐색으로 풀게된다면 dfs나 bfs나 똑같이 된다. 따라서 다른 방법이 필요했다. 이진탐색을 이용해서 중량을 결정하고 탐색 ..
-
-
백준 5829(Luxury River Cruise)전공/알고리즘 2020. 9. 24. 00:49
www.acmicpc.net/problem/5829 5829번: Luxury River Cruise Farmer John is taking Bessie and the cows on a cruise! They are sailing on a network of rivers with N ports (1 3 -> 2(시작) -> 3 -> 4 -> 3(시작) -> 4 -> 1 -> 4 -> 1 -> 2 -> 1(시작) 어떤 점에서 시작을 한다고 하고, 그 점에서 이미 시작을 하였다면 주기반복이다. 왜냐면 어떤 점에서 M의 이동을 하여서 목적지로 이동을 한다고 하면 M의 순서는 변하지 않고, 그래프도 그대로 있으니깐 당연하다. 따라서 주기를 찾으려면 일단 모든 시작점에서 M번의 간선을 지났을 때 목적지를 구하고, ..
-
#671 div2 9/19대회/코드포스 2020. 9. 24. 00:39
codeforces.com/contest/1419 Dashboard - Codeforces Round #671 (Div. 2) - Codeforces codeforces.com 왜 이리 늦게 후기를 쓰냐면 보고 멘붕이 와서 30분동안 멍때리다가 게임을 엄청 했다..... 아직도 그때 그 여파가 남아있는 것 같다. 일단 문제해석이 안되었다. 원래 영어를 못하는데 급하게 하려니깐 고등학교때 습관이 나왔다. 해석 안 되어도 넘어가서 해석 된것처럼 행동하는 버릇 계속 공부하면서도 못 버린 그 몹쓸버릇 A를 해석하는데 엄청나게 오래걸린 뒤에 B를 해석하는데 도무지 nice한거의 조건을 몰랐다. 이것만 주구장창 생각하고 있으니깐 코포가 종료되었다. nice한 조건은 인접한 사각형의 크기가 모두 다를때였는데, 그렇게..
-
브루트포스 159p 게임판 덮기전공/종만북 2020. 9. 18. 15:19
algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 �� algospot.com 역시 완전탐색을 위한 문제. 중복을 피하기 위한 방법이 제일 중요한 문제였다. 가장 왼쪽 위부터 채워나갔다. #include using namespace std; #define MAX 25 int T, H, W; bool game[MAX][MAX]; int solve(int num) { if (num == 0) return 1; int ret = 0; int ..
-
브루트포스 155p 소풍전공/종만북 2020. 9. 18. 15:16
algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 algospot.com 친구끼리만 짝이 되게끔 만들어야 한다. 친구끼리만 짝이 되는 경우의 수는? 모든 경우를 다 따진 후에 친구끼리만 짝 되었을 때 세면 된다. brute force 를 사용할 수 있는 경우는 입력이 작아서, 시간초과가 나지 않을때는 가능한 것 같다. 위 문제는 이걸 위해서 만들어진 문제기 때문에 상관없다만 조심하자 아 그리고 또 항상 주의해야 할것이 중복되게 세지 않는 것이다. 중복이 생기는 ..