백준 문제풀이

태그 DP, 조합론 문제 정리 크리스마스 트리의 i층에는 i개의 칸이 있으며, 각 칸에는 색깔을 배치할 수 있다. 또한, 어떤 층에 놓여 있는 색깔은 그 수가 같아야 한다. 트리의 크기와 빨강, 파랑, 초록의 개수가 주어질 때, 트리를 장식하는 경우의 수를 구하는

MSTN개의 도시가 있고, 각 도시 사이에는 고속철도가 이미 깔려있는 곳이 있고 깔리지 않은 곳이 있다. 여기에 임의의 도시에서 다른 임의의 도시로 이동할 수 있게 고속철도를 추가로 설치하려고 한다. 고속철도 설치에 필요한 최소 비용을 구하는 문제이다."임의의 도시에서

https://www.acmicpc.net/problem/2258그리디, 정렬고기가 N덩어리 있다. 또한 어떤 고기를 샀을 때, 그 고기보다 싼 가격을 가지는 고기는 전부 덤으로 받을 수 있다. 고기 무게를 M 이상 사려고 할 때, 필요한 최소 비용을 구하는

https://www.acmicpc.net/problem/2335DP, 그리디아버지는 원형 정원을 M개, 직선형 정원을 K개 가지고 있다. 각 정원에는 사이프러스 나무가 일정 간격으로 심겨져 있고, 서로 이웃한 두 사이프러스 나무 사이에는 항상 올리브 나무가

그리디, 정렬남자와 여자가 각각 N명씩 있다. 어떤 남자들은 자기보다 키가 큰 여자와 춤을 추고 싶어하며, 어떤 남자들은 자기보다 키가 작은 여자와 춤을 추고 싶어한다. 여자도 마찬가지이다. 남녀 모두 조건을 만족할 때, 만들 수 있는 매칭의 개수의 최대값을 구하는 문

문제 정보 https://www.acmicpc.net/problem/3197 BFS BFS, 분리 집합 문제 정리 Y행 X열 격자에 백조가 두 마리 살고 있다. 호수 얼음으로 덮여 있으며, 매일 물과 맞닿아 있는 얼음이 한 겹씩 녹아 물이 된다. 백조는 물에서만 상하좌우로 이동할 수 있을 때, 두 백조가 만날 수 있는 최소 날짜를 구하는 문제이다. 풀...

https://www.acmicpc.net/problem/3552기하학, 스위핑검은 픽셀로만 이루어진 W\*H 크기의 격자 위에 원을 N개 그리려고 한다. 원의 중심 $$(x_c, y_c)$$에 대해 $$\\sqrt{(x_c-x)^2 + (y_c-y)^2} \

https://www.acmicpc.net/problem/6501다익스트라, BFS운전자는 매일 이동한 시간이 600분 이하가 되어야 하며, 날마다 이동이 끝나면 체인점 호텔이 있는 도시에서 쉴 수 있다. 이 조건을 만족시키면서 1번 도시 -> N번 도시까지

문제 정보 https://www.acmicpc.net/problem/7187 BFS, 선분 교차 판정 문제 정리 2차원 얼음판 위에 퍽이 있다. 1초에 한 번 동, 서, 남, 북 중 한 곳에서 퍽을 두드릴 수 있고, 두드리지 않아도 된다. 퍽은 두드린 방향과 반대

https://www.acmicpc.net/problem/7346DP각 테스트케이스마다 유전자 서열 A와 B가 주어진다. 유전자 서열의 곳곳에 \*을 추가할 수 있으며, 문제에 나온 표에 따라 두 유전자 서열의 유사도를 계산할 수 있다. 이 \*을 적절히 추가

https://www.acmicpc.net/problem/7989DPN명의 사람이 배를 이용해 강을 건너려고 한다. 배는 한 번에 최대 2명까지 이동할 수 있고, 두 명이 함께 이동하면 걸리는 시간은 둘 중 큰 값을 가진 사람만큼 걸린다. 모든 사람을 강 건너

문제 정보 https://www.acmicpc.net/problem/12982 그리디, 브루트포스, 정렬 문제 정리 K개의 색의 공이 여러 개 주어진다. 한 박스에는 공을 최대 K개까지 담을 수 있고, 박스 안의 공은 모두 같은 색이거나 모두 다른 색이어야 한다.

https://www.acmicpc.net/problem/13312해 구성하기자구이는 정수 N개를 전부 더한 뒤 100으로 나눈 값의 아크코사인 값을 계산하는 문제를 받았다. 그러나 자구이는 각각의 정수를 100으로 먼저 나눈 뒤 다 더하는 방식으로 잘못 계산

MSTN개의 DNA가 주어지며, unlikeliness값이 최소가 되도록 트리를 만드는 문제이다. unlikeliness값은 트리를 구성하는 간선들의 가중치 합을 의미하며, 각 간선은 두 DNA에서 문자가 서로 다른 위치의 개수이다. 말이 길지 그냥 MST 만들고 MS

https://www.acmicpc.net/problem/32208애드 혹3차원 좌표 공간 (0, 0, 0)위에 나이트가 놓여 있다. 이 나이트는 x, y, z 좌표 중 하나는 $$\\pm1$$, 다른 하나는 $$\\pm2$$, 나머지 하나는 $$\\pm3$$

https://www.acmicpc.net/problem/33706그리디정점 N개, 간선 M개로 이루어진 무방향 그래프가 주어진다. 간선의 비용을 양의 정수중에 마음대로 정할 수 있을 때, i < j인 정점에 대해 1 -> i 비용이 1 -> j 비용보다

https://www.acmicpc.net/problem/34006BFS, 역추적봄의 기운, 여름의 기운, 가을의 기운이라는 이름의 게이지 3개가 있으며, 세 게이지의 합은 항상 3N이다. 궁기의 공격에 피격당하면 봄의 기운이 +a, 가을의 기운이 -a만큼 변

https://www.acmicpc.net/problem/3866DP풍선이 총 N개 떨어지며, i번째 풍선은 $$t_i$4의 시간에 $$p_i$$의 위치에 떨어진다. 풍선이 땅에 닿는 순간 로봇이 같은 위치에 있어야 풍선을 잡을 수 있고, 그렇지 않으면 게임이

https://www.acmicpc.net/problem/2203무작위화, 정렬DP, 정렬도시가 3N개 있고, 각 도시의 인구는 1,000명이다. 각 도시의 월드당 지지자 수가 주어질 때, 도시를 N개씩 세 선거구로 나눈다.어떤 선거구에서 월드당 지지자 합이

https://www.acmicpc.net/problem/32582최대 유량(?), 수학양들이 목장 안으로 들어온 늑대를 피해 도망치고 있다. 목장에는 울타리로 둘러싸인 통로들이 있으며, 이 통로들이 서로 연결되어 최종적으로 농장 마당으로 이어지는 하나의 출구

https://www.acmicpc.net/problem/6818스위핑, 기하학2차원 좌표평면에 K개의 무선장치가 달려 있으며, 각 무선 장치는 반지름이 R_i인 원 형태의 범위에 B_i의 세기로 신호를 쏴준다.Bob은 한 번에 여러 신호를 수신할 수 있으며

https://www.acmicpc.net/problem/3195매개변수 탐색수직선 위에 N개의 마을이 있다. 이 마을들은 매년마다 B_i톤만큼의 물고기가 남기 때문에 각 마을마다 K명씩 아이들을 데려와 남는 물고기를 먹이려고 한다. 아이들은 1년에 1톤의 물

https://www.acmicpc.net/problem/16516수학, 애드 혹Lipschitz 상수는 다음 식을 만족하는 실수 L의 최소값을 의미한다.$$|f(x) - f(y)| \\leq L \\cdot |x-y|$$좌표 N개가 주어질 때, Lipschi

문제 정보 https://www.acmicpc.net/problem/16117 DP, 많은 조건 분기 문제 정리 N행 M열의 격자에 일정한 간격으로 실버 주머니들이 놓여 있다. 이 실버 주머니들은 1초에 한 칸씩 이동하는 속도로 동일하게 떨어지고 있다. 시작점을 잡

https://www.acmicpc.net/problem/30788DP, 역추적앨범아트를 지나는 N개의 축이 주어지며, i번째 축이 수평선과 이루는 각도는 $A_i$이다. N개의 축을 각각 정확히 한 번 사용하여 대칭이동할 때, 앨범아트를 원래 상태로 만들 수

https://www.acmicpc.net/problem/27654매개 변수 탐색, 이분 탐색각 시험 i는 $(P_i, Q_i)$로 주어지며, 이는 "총 $Q_i$ 문제 중 $P_i$개 정답"을 의미한다.시험 집합 $X$의 평균 성적은 다음과 같이 정의된다.$

https://www.acmicpc.net/problem/27654매개 변수 탐색, 이분 탐색주어진 이미지 두 개의 경계선을 설정하고 2픽셀 이상 포개어 부자연스러움 정도를 최소로 만들어야 한다. 위 그림과 같이 경계선 픽셀은 바로 윗 행의 경계선 픽셀과 좌우

https://www.acmicpc.net/problem/21886수학, 누적 합카운트다운 타이머가 있다. 타이머는 처음에 k초로 설정되며, t초가 지난 경우 시간은 max(k-t, 0)이다. 이 타이머를 시작한 뒤 n번 특정한 시간에 타이머를 확인했고, 그때

https://www.acmicpc.net/problem/3572세그먼트 트리크기가 $H \\times W$인 게시판이 있고, 여기에 크기가 $1 \\times w_i$ 인 직사각형 모양의 공지사항을 $N$개 붙이려고 한다. 공지사항을 붙일 때는 아래와 같은

https://www.acmicpc.net/problem/17400세그먼트 트리, 홀짝성깃발춤 공연은 카리스마가 $c_i$의 값을 가진 N명의 사람들이 일렬로 서서 진행하는 공연이다.깃발춤 공연 중 교대 깃발춤 동작이 있는데, 구간 L, R의 사람들이 깃발을

https://www.acmicpc.net/problem/31838DP, 누적 합무한히 긴 수직선 위에 N개의 아이템이 구간 1, N에 떨어져 있으며, 각 아이템의 가치는 $A_i$의 값을 가진다.또한, 아이템을 주울 수 있는 집게가 있는데, 길이가 K인 집게

https://www.acmicpc.net/problem/21342연결 리스트, 우선순위 큐수직선 위에 $N \\leq 100,000$개의 드론이 일정한 속도로 움직이고 있다.두 드론이 같은 위치에 도달하는 순간 충돌하며 사라지게 된다.드론의 초기 위치와 속도

https://www.acmicpc.net/problem/4995기하학, 브루트포스아래 사진처럼 2차원 평면 위에 N개의 점이 있을 때, 반지름이 1인 원으로 점을 최대 몇 개까지 포함시킬 수 있는지 구하는 문제이다.한 가지 관찰을 할 수 있다.최적해는 어떤

https://www.acmicpc.net/problem/26076BFS곰곰이는 0 위치에 있고, 상하좌우 4방향으로 이동할 수 있다. 또한, 곰곰이는 Y 위치에 놓인 치킨을 먹으러 이동하려고 한다.곰곰이가 치킨을 먹을 수 없도록 장애물을 설치해 접근할 수 없

https://www.acmicpc.net/problem/24782백트래킹, 브루트포스그래프가 주어지고 아래 규칙에 따라 정점을 색칠해야 한다.두 정점이 이어진 간선이 존재할 때, 이 정점들은 같은 색으로 칠할 수 없다.이를 만족하면서 그래프의 정점을 전부 칠

https://www.acmicpc.net/problem/24782백트래킹, 브루트포스길이가 2K인 문자열 N개가 주어진다.그래프의 정점에 글자를 하나씩 할당할 때, 아래 조건을 만족하는 그래프의 정점 개수로 가능한 최소값을 구하는 문제이다.첫 정점의 in-d

문제 정보 https://www.acmicpc.net/problem/2409 이분 탐색, DFS 문제 정리 긴 파이프 M개를 잘라 짧은 파이프를 최대한 많이 만들려고 할 때, 만들 수 있는 파이프의 최대 개수를 구하는 문제이다. 풀이 관련 구글 검색을 좀 많이 한