Problem Solving/Baekjoon Online Judge (Gold) (68) 썸네일형 리스트형 백준 27728 - 개구리와 쿼리 (C++) 문제 문제 링크 BOJ 27728 - 개구리와 쿼리 문제 요약 $N \times N$ 크기의 $2$차원 배열에 대해 아래와 같은 $Q$개의 쿼리가 주어진다. 각 쿼리의 답을 출력하자. $S_x$ $S_y$ $L$ : 개구리의 초기 위치가 $\left(S_{x},S_{y}\right)$ 이고 최대 한번 $L$ 이상의 양의 정수 값 $T$만큼 점프할 수 있을 때 육지에 도달하는 데 걸리는 최단 시간을 출력하라. 제한 TL : $1$ sec, ML : $128$ MB $3 ≤ N ≤ 500$ $1 ≤ Q ≤ 200,000$ $0 ≤ A_{ij} ≤ 10,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 누적 합(prefix_sum) 풀이 쿼리에 대해 나이브하게 답한다고 생각해보자. 그럼 단순히 $O(N^2Q).. 백준 30869 - 빨리 기다리기 (C++) 문제 문제 링크 BOJ 30869 - 빨리 기다리기 문제 요약 $N$개의 버스 정류장에 대해 $M$개의 버스 노선 정보가 주어진다. '빨리 기다리기'를 최대 $K$번까지 사용할 수 있을 때, $1$번 정류장에서 $N$번 정류장까지 가는 데에 걸리는 최소 시간을 구해보자. 제한 TL : $2$ sec, ML : $1024$ MB $2 ≤ N ≤ 500$ $0 ≤ K ≤ 500$ $1 ≤ M ≤ 250,000$ $1 ≤ t_i, g_i ≤ 10,000$ 알고리즘 분류 그래프 이론 (graphs) 다익스트라 (dijkstra) 풀이 그래프에서 두 정점쌍 간의 최단 거리는 기본적으로 다익스트라를 이용해 쉽게 구할 수 있다. 그런데 이번 문제에선, 고려해야 할 것들이 조금 있다. 간선마다 배차 간격이 존재한다. .. 백준 30621 - 어? 금지 (C++) 문제 문제 링크 BOJ 30621 - 어? 금지 문제 요약 $N$개의 시각에 대해 수열 $t_N, b_N, c_N$이 주어진다. 성우가 규칙을 지키는 선에서 대회장에 줄 수 있는 최종 혼란의 최댓값을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 100,000$ $1 ≤ t_i, b_i, c_i ≤ 10^9$ $t_{i-1} < t_i;$ $b_i ≤ t_i$ 알고리즘 분류 다이나믹 프로그래밍 (dp) 이분 탐색 (binary_search) 풀이 어떤 시각 $t_i$에서, 선택할 수 있는 분기 방향을 생각해보자. 이는 다음과 같을 것이다. '어?'를 외치지 않는다. 지금부터 '어?'를 처음 외친다. 두 번째 경우의 연장선인데, $(t_i - b_i)$부터 지금까지 '.. 백준 30622 - Rush & Slash (C++) 문제 문제 링크 BOJ 30622 - Rush & Slash 문제 요약 $2$차원 상의 잡초들의 좌표 $(x_i, y_i)$가 $N$개 주어진다. 일련의 과정을 따라, 모든 잡초들을 제거하기 위해 이동해야 하는 거리의 합의 최솟값을 구해보자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N ≤ 10^5$ $-10^9 ≤ x_i, y_i ≤ 10^9$ 주어지는 모든 좌표는 서로 다르다. 알고리즘 분류 자료 구조 (data_structures) 트리를 사용한 집합과 맵 (tree_set) 분리 집합 (disjoint_set) 풀이 모든 좌표 $(x_i, y_i)$에 대해, 해당 좌표를 기준으로 $8$방향을 보며 인접한 좌표가 주어졌는지 확인하자. $x_i$와 $y_i$의 좌표 범위에 따.. 백준 30461 - 낚시 (C++) 문제 문제 링크 BOJ 30461 - 낚시 문제 요약 $N*M$개의 칸 각각에 존재하는 물고기의 정보가 주어진다. $Q$개의 쿼리에 대해, 미끼를 회수할 때까지 몇 마리의 물고기가 사로잡히는지 출력하자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N,M ≤ 2,000$ $1 ≤ Q ≤ 300,000$ $0 ≤ a_{ij} ≤ 500$ 알고리즘 분류 다이나믹 프로그래밍 (dp) 누적 합 (prefix_sum) 풀이 $dp[i][j]$에 $Q(i, j)$의 답을 저장한다고 생각해보자. 계단식으로 답을 계산할 수 있으므로, 먼저 $dp[i][j]$는 $dp[i - 1][j - 1]$을 포함한다. 여기에 추가적으로 $A[i][j] + A[i - 1][j] + A[i - 2][j] + .... 백준 30464 - 시간낭비 (C++) 문제 문제 링크 BOJ 30464 - 시간낭비 문제 요약 $a_1, a_2, ... , a_N$이 주어진다. 각 $a_i$에서는 해당 칸에 적힌 칸만큼 바라보는 방향으로 이동할 수 있다. 바라보는 방향을 최대 두 번 반전할 수 있을 때, $a_1$에서 $a_N$에 최대한 늦게 도착하는 경우를 찾아보자. 제한 TL : $1$ sec, ML : $1024$ MB $3 ≤ N ≤ 200,000$ $0 ≤ a_i ≤ 200,000$ 알고리즘 분류 다이나믹 프로그래밍 (dp) 풀이 어떤 위치에서 고려해야할 상태는 $3$가지가 있다고 생각했다. 어느 위치$?$ 어느 방향$?$ 지금까지 몇 번 반전$?$ 이에 따라, 다음과 같이 점화식을 정의하자. $dp[u][p][q] :$ $a_u$에서, 방향 $p$를 바라보고 .. 백준 25606 - 장마 (C++) 문제 문제 링크 BOJ 25606 - 장마 문제 요약 $N$일동안 비가 내린다. 장마 시작 $t$일 후 내리는 비는 상자에 $a_i$만큼 물을 채운다. 보관된 상자에선 매일 $M$만큼의 물이 증발할 때, 아래 두 쿼리를 수행하는 프로그램을 작성하자. $1$ $t$ : 장마 시작 $t$일 후, 모든 상자에 들어있는 물의 양의 합은 무엇인가$?$ $2$ $t$ : 장마 시작 $t$일 후, 모든 상자에서 증발하는 물의 양의 합은 무엇인가$?$ 제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 10^5$ $1 ≤ M, a_i ≤ 10^4$ 알고리즘 분류 누적 합 (prefix_sum) 풀이 쿼리가 들어올 때마다 답을 계산하기엔 조금 귀찮아 보인다. $N ≤ 10^5$이고 각 $N_i$.. 백준 29811 - 지각하기 싫어 (C++) 문제 문제 링크 BOJ 29811 - 지각하기 싫어 문제 요약 애지문부터 대운동장까지 가는 경로 $N$개, 대운동장부터 ITBT관까지 가는 경로 $M$개가 주어진다. 아래의 쿼리를 수행하는 프로그램을 작성해보자. $U$ $x$ $y$ : $x$번 경로의 인구를 $y$로 바꾼다. $L$ : 애지문에서 ITBT관까지 가는 가장 빠른 경로가 $a, b$번 경로를 통해 이동할 때일 때, $a, b$를 출력한다. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N, M ≤ 100,000$ $1 ≤ Q ≤ 200,000$ 알고리즘 분류 자료 구조 (data_structures) 트리를 사용한 집합과 맵 (tree _ set / map) 풀이 먼저 주어지는 $N$개의 경로를 관리할 집합과, 나중에 .. 이전 1 2 3 4 ··· 9 다음