본문 바로가기

분류 전체보기

 (236)
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 배열을 잡기에는 무리가 있다. 그래서 나는 그리디로 한 번 도전 해 보았는데, 다행이게도 맞았습니다를 받았다. 먼저 가장 큰 큐브부터 박스에 넣을 수 있다면, 박스에 넣어주고 남는 공간을 재귀로 호출한다. 만약 박스에 큐브를 채워 넣으..
알고리즘 스터디 - 큐 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 솔루션 처음에 접근법이 잘 안떠올라 고생했다. 기존의 BFS와 유사한데, 복사라는 기능이 추가되어 까다로웠다. 나는 2차원 배열로 잡고, 우선순위 큐를 이용해 해결하였다. 우선순위 큐는 {텍스트 길이, 복사된 문자 길이, 총 시간} 으로 잡고 정렬 순서는 시간이 가장 작은 것이 top에 위치 하도록 하였다. 그리고 시작은 {1,0,0}으로 시작하여서 다음 3가지 경우로 나눴다. 1. 현재 이모티콘을..
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개를 ..
우선순위 큐 문제 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 솔루션 N^2의 격자판에서 N번째로 큰 수를 뽑아야 한다. 처음에 모든 수를 다 담은 뒤, 5번 째 큰 수를 뽑으려 했는데, 메모리 제한이 12MB인 것을 모르고 제출을 했다가.. 메모리 초과를 받았다. 따라서 우선순위 큐를 이용해 이를 해결하였는데, 원리는 다음과 같다. 입력으로 들어온 수 중에서 가장 큰 수 N개만 남겨놓고 모든 값들은 우선순위 큐에서 제거한다. 그러면 N번째 큰 수가 자동으로 ..

티스토리툴바