GitHubSeob

문제 https://www.acmicpc.net/problem/1932   문제풀이 맨 위층부터 시작해서 아래에 있는 수를 선택해가며 내려가고, 합한 값 중 최댓값을 출력하는 문제이다.DP를 이용해서 해당 삼각형을 편하게 2차원 벡터로 나타내면73 88 1 02 7 4 44 5 2 6 5이런식으로 나타낼 수 있다.위에서 아래로 이동하므로 DP[y][x]의 값은 한 칸 위 또는 왼쪽 위 대각선 한 칸 중 큰 값을 더하면 된다.따라서 식으로 나타내면 Arr[y][x] + DP[y-1][x-1], DP[y-1][x]이 된다. 코드#include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL)..

문제 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 문제풀이 테이프를 자르거나 겹쳐서 붙이는 것은 굳이 생각 안 해도 된다. 물을 막을 때, 그 위치의 좌우 0.5만큼 간격을 주면 1만큼의 테이프가 필요 없다고 생각하면 된다. 따라서 입력받은 테이프의 길이를 1 빼준다. 그다음 정렬을 해서 왼쪽부터 테이프를 붙인다. 테이프를 붙이게 되면 위치를 저장해 놓고 다음 구멍에 갔을 때, 이미 테이프가 붙여져 있는지 확인을 한다. 안 ..

문제 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제풀이 소수의 개수를 구하는 문제이다. 0을 입력받기 전까지 계속 입력을 받으므로 소수를 미리 구하는 것이 좋아 보인다. 따라서 에라토스테네스의 체를 이용해 입력의 최댓값 123456 * 2인값까지 중 소수를 구한다. vectorisPrime(246913, true); for (int idx = 2; idx

문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 문제풀이 경우의 수를 나눠 DP 하는 문제인 줄 알았는데 총개수를 세고 나니까 단순히 DP 하면 되는 문제였다. N이 1일 때 배치 X: 1 한 마리 배치: N*2 = 2 = 3 N이 2일 때 배치 X: 1 한 마리 배치: N*2 = 4 두 마리 배치: 2 = 7 N이 3일 때 배치 X: 1 한 마리 배치: N*2 = 6 두 마리 배치: 8 세 마리 배치: 2 = 17 이런 식으로 개수를 세면 규칙이 보인다. answer[N] = answer[N-1]*2 + answer[N-2] 코드 #include #include #def..

문제 https://www.acmicpc.net/problem/24498 24498번: blobnom 블롭들은 심심해서 서로를 이용해 $N$개의 탑을 만들었다. 각 탑의 높이는 그 탑에 있는 블롭의 수와 같다. 여러분은 다음 행동을 $0$회 이상 할 수 있다. 처음과 마지막이 아닌 탑 중 하나를 선 www.acmicpc.net 문제풀이 맨 처음과 맨 끝을 제외한 탑에 있는 블롭의 수 + 인접한 두 타워 중 블롭의 최솟값을 더한 값 중 최댓값을 구하는 문제이다. 조심할 점은 인접한 블롭수를 더하지 않는 맨 처음 또는 맨 끝에 있는 탑의 블롭수가 정답일 수도 있다는 점이다. 먼저 answer에 맨 처음 타워인 tower[0], 맨 끝 타워인 tower.back() 중 최댓값을 저장해 놓는다. 그다음 1부터 ..

문제 https://www.acmicpc.net/problem/2428 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net 문제풀이 두 파일이 있을 때 두 조건을 만족해야 한다. 1. 작은 파일 = 큰 파일 * 0.9 따라서 이분 탐색인 lower_bound를 이용하여 문제를 푼다. 모든 입력을 받았으면 sort를 통해 오름차순으로 정렬한다. 0번째 파일부터 N-1번째 파일까지 탐색을 한다. 탐색하는 idx번째 파일을 큰 파일로 둔다. 그렇다면 ..

문제 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제풀이 연속된 K개만큼의 누적합 중 가장 큰 값을 구하는 문제이다. 먼저 온도를 입력받는다. 0번 온도부터 K개만큼 온도의 합을 sum에 누적 합한다. 그다음 현재 누적합에서 가장 처음에 더한 값을 뺀다. (idx - K 번째 온도) idx - K번째 온도값을 뺐으니 idx번째 온도를 더해 더한 온도의 개수를 K로 맞춘다. max 함수를 이용해 answer의 최댓값을 갱신한다...

문제 https://www.acmicpc.net/problem/5464 5464번: 주차장 시내 주차장은 1부터 N까지 번호가 매겨진 N개의 주차 공간을 가지고 있다. 이 주차장은 매일 아침 모든 주차 공간이 비어 있는 상태에서 영업을 시작하며, 하룻동안 다음과 같은 방식으로 운영 www.acmicpc.net 문제풀이 우선순위 큐, 큐를 이용하여 풀었다. 생각보다 고려해야 될 것이 있던 문제였다. 주차장 자리가 없을 때 차량이 들어오는 것도 고려해야 하고, 주차장 자리가 여러 개일 때도 고려해야 했다. 우선순위 큐 remain은 남은 주차장을 나타낸다. 남은 주차장은 번호가 작은 주차장이 우선순위큐의 top부분에 오게 된다. ({번호, 요금}) 큐 waiting은 남은 주차장이 없어 대기를 하고 있는 차..

문제 https://www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 문제풀이 처음에는 이중 반복문으로 풀었는데 시간 초과가 나서 투 포인터를 이용해 풀었다. pair를 이용해 벡터에 앞부분에는 좌표, 뒷부분에는 얼음양을 입력받는다. 백곰은 한번 정한 자리에서 -K ~ +K 부분까지만 이동할 수 있다. 입력은 좌표순이 아니므로 sort함수를 이용해 좌표를 오름차순으로 정렬한다. 먼저 left, right를 0으로 정한 뒤 left, right를 움직이며 범위를 정한다. 만약 left..