본문 바로가기

백준

 (221)
C++[백준] 28216번 아이템 획득 https://www.acmicpc.net/problem/28216 28216번: 아이템 획득 $N ≤ 2\,000$, $Q ≤ 2\,000$, $x_i ≤ 1\,000$, $y_i ≤ 1\,000$, $w_i ≤ 10$, 매 순간 자동차의 $x$, $y$좌표는 $1\,000$ 이하이다. www.acmicpc.net 솔루션 지나가는 모든 셀에 대해서 탐색하여(완전탐색) 답을 계산하였으나, 9점을 받았다. 그래서 태그를 봤는데,, 이분탐색 + 누적합을 보니 아이디어가 바로 떠 올랐다. 입력을 배열 두개 모두에 담는다. 그리고 각각의 배열중 하나는 X축 기준으로 정렬, 하나는 Y축 기준으로 정렬한다. 자동차는 축에 평행하여 움직이기 때문에 X축으로만 움직일 땐, Y축으로 정렬된 배열에서 이분탐색으로 시작과 ..
C++[백준]26972번 Barn Tree https://www.acmicpc.net/problem/26972 26972번: Barn Tree Farmer John's farm has $N$ barns ($2 \leq N \leq 2\cdot 10^5$) numbered $1 \dots N$. There are $N-1$ roads, where each road connects two barns and it is possible to get from any barn to any other barn via some sequence of roads. Currently, the $j$th barn h www.acmicpc.net 솔루션 창고가 N개, 길의 개수가 N-1개, 모든 창고는 이동 가능하다는 조건 때문에 트리라는 것을 유추 할 수 있다. 나는..
C++[백준]11025번 요세푸스 문제 3 https://www.acmicpc.net/problem/11025 11025번: 요세푸스 문제 3 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000,000) www.acmicpc.net 솔루션 https://en.wikipedia.org/wiki/Josephus_problem Josephus problem - Wikipedia From Wikipedia, the free encyclopedia Mathematical counting-out question Claude Gaspar Bachet de Méziriac's interpretation of the Josephus problem with 41 soldiers and a step size of 3, s..
C++[백준]1727번 커플 만들기 https://www.acmicpc.net/problem/1727 1727번: 커플 만들기 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다. www.acmicpc.net 솔루션 해당 문제를 접하기 전에 먼저 풀었던 문제가 있는데, (https://www.acmicpc.net/problem/8902) 그 문제와 유사해서 접근은 금방 할 수 있었다. 먼저 남/여 중 더 적은 것은 v0배열에 담고, 다른 것은 v1 배열에 담는다 그리고 각각 정렬을 해 준다. 이를 통해 i j +1 과 i+1 j일 경우는 없어지며, (꼬인 형태로 매칭되지 않으며) 남은 부분의..
C++[백준]1493번 박스 채우기 https://www.acmicpc.net/problem/1493 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net 오랜만에 포스팅.. 솔루션 처음에 정육면체 자르기와 비슷하다 생각하여 DP로 생각해 보았지만, 입력 값이 10^6이라고 해서 dp 배열을 잡기에는 무리가 있다. 그래서 나는 그리디로 한 번 도전 해 보았는데, 다행이게도 맞았습니다를 받았다. 먼저 가장 큰 큐브부터 박스에 넣을 수 있다면, 박스에 넣어주고 남는 공간을 재귀로 호출한다. 만약 박스에 큐브를 채워 넣으..
C++[백준]20529 가장 가까운 세 사람의 심리적 거리 https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net 솔루션 비둘기 집을 이용하여 문제를 해결해야 했다. 비둘기 집은 경우의 수가 K개이고 입력이 K 를 초과하면 무조건 중복되는 값이 존재한다는 뜻이다. 처음에 생각하기에 MBTI가 16가지이므로 , 16~31, 32~ 47, 48 ~... 이렇게 나눌려고 했었지만, 코드로 짜기에는 너무 귀찮았다. 그런데, 입력이 48 이상인 경우는 무조건 0이 되고, 나머지는 48C3 이므로 충분히 돌아갈 것이라 생각을 했고, 그냥 48미만이면 완전 탐색으로 해결하였다. 48개 미만이면, N과M 처럼 3개를 ..
C++[백준]20303번 할로윈의 양아치 https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 솔루션 친구들을 하나의 묶음으로 묶고 냅색을 수행하면 된다. 1. bfs를 이용해 그룹의 인원과, 사탕의 총 개수를 구한다. 2. 냅색을 이용한다.. (오랜만에 글을 써서.. 그런가.. 엄청 짧다..) 코드 #include #include #include using namespace std; int N, M, K..
C++[백준]1915번 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 솔루션 dp 문제로, 가장 큰 정사각형을 만들 수 있는 한 변의 길이를 저장하면서 dp 테이블을 채워 나간다. 그리고 만들 수 있는 정사각형의 한 변의 길이를 구하는 점화식은 대각선 위, 위, 왼쪽 중 가장 작은 값에서 +1 을 해 주면 된다. 코드 #include using namespace std; int N, M; int arr[1002][1002]; int dp[1002][1002]; int main() { ios_base::sync_with_stdio(fal..

티스토리툴바