Problem Solving/Baekjoon Online Judge (Gold) (70) 썸네일형 리스트형 백준 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$개의 경로를 관리할 집합과, 나중에 .. 백준 29618 - 미술 시간 (C++) 문제 문제 링크 BOJ 29618 - 미술 시간 문제 요약 칸의 길이 $N$과 아래와 같은 $Q$개의 쿼리가 주어진다. 모든 쿼리의 처리가 끝난 후 각 칸의 상태를 출력하자. $a$ $b$ $x$ : $a$번째 칸부터 $b$번째 칸까지, 색칠되지 않은 칸을 $x$번 색으로 칠한다. 제한 TL : $0.5$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 100,000$ $1 ≤ x ≤ 10^9$ 알고리즘 분류 자료 구조 (data_structures) 트리를 사용한 집합과 맵 (tree _ set / map) 풀이 제한을 보면 당연히 나이브하게 돌 수 없다. 간단하게, $std::set$에서 색칠되지 않은 칸들을 들고 있다고 해보자. 그럼 임의의 쿼리 $a_i, b_i, x_i$에서 $a_i$의 .. 백준 28472 - Minimax Tree (C++) 문제 문제 링크 BOJ 28472 - Minimax Tree 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 이 트리로 $Minmax$ $Tree$를 구성할 때, 각 정점의 답을 묻는 $Q$개의 쿼리에 답해보자. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 10^5$ $1 ≤ Q ≤ 10^5$ $0 ≤ t_i ≤ 10^9$ 알고리즘 분류 다이나믹 프로그래밍 (dp) 트리 (trees) 트리에서의 다이나믹 프로그래밍 (dp_tree) 풀이 기본적인 $TreeDP$ 문제이다. 문제에서 친절하게 규칙을 나열해주므로, 이를 그대로 코드에 옮겨주면 되겠다. 구체적으로 루트의 깊이를 $1$이라고 할 때, 리프 노드를 향해 내려가며 현재 깊이가 홀수라면 자식 노드의 최댓값을 현재.. 백준 28467 - Spell Cards (C++) 문제 문제 링크 BOJ 28467 - Spell Cards 문제 요약 $N$장의 카드가 단 하나만 남을 때까지 인접한 두 카드에 대해 마법을 시전한다. 최종적으로 소모하는 총 마력의 최솟값을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 400$ $1 ≤ a_i ≤ 10^9$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 BOJ 11049 - 행렬 곱셈 순서 와 비슷한 느낌을 받았다면 충분하다. 식 정의에만 조금 차이가 있을 뿐, 본질적으로 비슷한 형태로 풀 수 있다. $dp[p][q]$ : 구간 $[p, q]$ 에서의 답. 어떤 구간에 대해, $p == q$ 가 아닌 이상 반드시 두 연속 부분 수열로 나누어 답을 구할 수 있다. 구체적으로 구간 $[p, q]$의 답.. 백준 28707 - 배열 정렬 (C++) 문제 문제 링크 BOJ 28707 - 배열 정렬 문제 요약 길이가 $N$인 배열 $A = [A_1, A_2, ... A_N]$와 $M$가지의 조작 정보가 주어진다. 조작을 순서, 횟수에 상관없이 원하는만큼 적용할 수 있을 때, $A$가 비내림차순이 되도록 하는 데에 드는 최소 비용을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 8$ $1 ≤ M, A_i,c_i ≤ 10$ 알고리즘 분류 자료 구조 (data_structures) 그래프 이론 (graphs) 트리를 사용한 집합과 맵 (tree _ set / map) 다익스트라 (dijkstra) 풀이 오랜만에 참신한 문제를 만났다. 범위가 굉장한 힌트를 주지만 뭔가 구현이 답답할 수 있는데, 한 번 이렇게 생각해보자... 백준 23792 - K번째 음식 찾기 2 (C++) 문제 문제 링크 BOJ 23792 - K번째 음식 찾기 2 문제 요약 $x$ $y$ $z$ $k$ : 한식 $[1..x]$, 양식 $[1..y]$, 중식 $[1..z]$ 중에 $k$번째로 맛있는 음식 $?$ 한식, 양식, 중식 각각 $N$개의 음식에 대한 맛이 주어진다. 위의 쿼리가 $Q$개 주어질 때, 각각에 맞는 답을 출력하자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 10^5$ $1 ≤ A_x, B_y, C_z ≤ 2^{31} - 1$ $3N$개 음식의 맛은 모두 서로 다르다. 알고리즘 분류 이분 탐색(binary search) 매개 변수 탐색(parametric search) 풀이 K번째 음식 찾기 1 을 처음 보고 무지성 $merge$-$sort$ $tree$.. 백준 28421 - 곱하기와 쿼리 (C++) 문제 문제 링크 BOJ 28421 - 곱하기와 쿼리 문제 요약 $1$ $x$ : 수열에서 서로 다른 두 수 $A_i, A_j$를 곱하여 $x$를 만들 수 있으면 $1$, 없으면 $0$을 출력한다. $2$ $i$ : $A_i$를 $0$으로 바꾼다. 길이 $N$의 수열과 위의 두 유형으로 이루어진 $q$개의 쿼리가 주어진다. $1$번 쿼리가 주어질 때마다 그에 맞는 답을 출력하자. 제한 TL : $1.5$ sec, ML : $1024$ MB $0 ≤ x ≤ 10^8$ $1 ≤ N ≤ 10^5$ $1 ≤ A_i ≤ 10^4$ $1 ≤ Q ≤ 5*10^3$ 알고리즘 분류 수학(math) 정수론(number_theory) 풀이 $1$번 쿼리가 주어질 때마다 $x$를 인수 분해한다고 생각해보자. 이때 여러 인수 쌍.. 이전 1 2 3 4 5 ··· 9 다음