baekjoon(3)
-
BOJ 18785 : Clock Tree
https://www.acmicpc.net/problem/18785 18785번: Clock Tree In this example, Bessie can set all the clocks to point to 12 if and only if she starts in room 2 (for example, by moving to room 1, 2, 3, 2, and finally 4). www.acmicpc.net 상당히 어려운 문제였다.. 먼저 우리는 이러한 통로를 가면서 맞춰놓을 때, 처음 노드에서 출발해서 다시 돌아오는 방식임을 알 수 있다. 이때 왔다갔다 하면서 관찰할 수 있는 건 어떤 노드와 그 주변 노드가 하나 있을 때 둘 다 자신을 다 12시로 맞추기 위해서는 자신과 1차이나는 노드가 항상 있어야..
2022.09.03 -
BOJ 2618 : 경찰차
BOJ 2618 : 경찰차 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 아주 왤논 dp. 쫄고 있었는데 의외로 쉬워서 놀랐다. 환상의 듀엣 문제(먼저 보고 오는 걸 추천.)와 비슷한 느낌으로 dp를 해보자. dp[i][j] = i번째 사건을 1번 경찰차가, j번째 사건을 2번 경찰차가 담당할때 최적해. dist(i, j) = i번째 사건과 j번째 사건 사이의 유클리드 거리. nxt = 다음 사건. 이라고 정의한다면 dp[i][nxt] = min(dp[i][j] + dist(j, nxt), dp..
2021.04.30 -
BOJ 11570 : 환상의 듀엣
BOJ 11570 : 환상의 듀엣 11570번: 환상의 듀엣 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높 www.acmicpc.net dp로 풀 수 있다. dp[i][j] = i번째 음을 이가, j번째 음을 이가 불렀을때 최적해 A_i = i번째 음을 부를때 비용 nxt = 불러야 할 음 이라고 정의할 때, dp[i][nxt] = min(dp[i][j] + |A_nxt - A_j|, dp[i][nxt]) dp[nxt][j] = min(dp[i][j] + |A_nxt - A_i|, dp[nxt][j]) 코드 djayy035/dj035_PS 코드저장소. Contrib..
2021.04.30