KPU CE

문제 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 일단 크게 두가지 경우로 나뉜다. 1. 시간이 초과되서 상담을 그날 상담을 못하는 경우 2. 시간이 초과되지 않아서 그날에 상담을 할 수 있는 경우 일단 1번의 경우이다. 상담을 한다면 N보다 초과되어서 이날의 상담은 하지 못하므로 이날의 최대 dp의 값은 i+1의 값이 된다. -> 이날 상담을 안하고 다음 날 한다. 2번의 경우 1.상담을 할 수 있..

문제1 https://www.acmicpc.net/problem/17122 17122번: 체스 각 테스트 케이스에 대해, 주어진 두 칸이 같은 색이면 “YES”를, 아니면 “NO”를 출력하시오 (따옴표는 제외). www.acmicpc.net 문제 해결 체스판을 직접 3차원 배열로 구현하였다. A~H 부여하고 배열에서 직접 찾아 색깔을 알아내고 표기법2는 입력된 숫자의 위치를 찾아서 색깔을 알아냈다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include #include #include using..

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 해결 1~K까지 물건을 하나씩 넣어보면서 만약 물건의 무게가 더 크다면 패스 무게가 더 적다면 i-1값과 현재 현재 물건 가치 + 남은 무게의 dp값(하나씩 갱신 하므로 이 dp의 값은 남은 무게의 최대값이다.) 을 비교해서 더 큰 값을 dp에 넣는다. 이 방법을 K까지 반복하게 된다면 마지막 K무게에서의 마지막 물건의 ..

문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 해결 스택문제라서 최대한 스택으로 풀어보려 처음에는 선택한 수부터 선택한 수보다 큰 수가 나올 때까지 작은 수들을 스택에 넣은 다음 스택에 있는 수들을 차례대로 꺼내어 꺼낸 수의 인덱스~선택한 수보다 큰수 인덱스 까지 다시 오큰수를 구하는 알고리즘을 구현했는데 38%에서 시간초과가 나서 다른 블로그를 참고해서 풀었다.... 일단 처음 수를 스택에 넣는다. 그 다음수와 현재 수를 비교했을 때 만약 현재..

문제 https://www.acmicpc.net/problem/17124 17124번: 두 개의 배열 정수 배열 A 와 B가 있다. A는 총 n개의 서로 다른 양의 정수를 포함하고 B는 총 m개의 서로 다른 양의 정수를 포함한다. A, B를 이용해서 길이가 n인 새로운 배열 C를 만들어보자. C[i] 는 배열 B에 있 www.acmicpc.net 문제 해결 A[i]를 하나 택하고 A[i]보다 작은 것들 중에 가장 큰 B[j], A[i]보다 큰 것들 중에 가장 작은 B[j]가 답이다. 이것을 구하는데 큰것 작은것 두개의 이분탐색을 만들어서 두개의 절대값을 비교하였다. 만약 작은것 중에 A[i]보다 작은 것이 없으면 B 배열에서 가장 작은 값인 B[1] 만약 가장 큰 값이 없을 경우 문제에서의 최대값인 10..