C++97 [백준][스위핑] 1931 회의실 배정 c++구현 목차https://www.acmicpc.net/problem/1931문제 문제 접근 방향생각보다 아이디어가 잘 떠오르지 않았다. 하지만 N이 100000이라는 것을 보아 O(N) 시간으로 탐색해야 한다는 것을유추할 수 있다. 또한 경우를 줄이기 위해 정렬을 해야 한다는 것 또한 유추할 수 있다. 다음과 같이 3가지 정렬 기준이 나올 수 있다. 1. 시작점 기준으로 정렬하기바로 반례가 나온다. 경우에서 제외시켜 준다. 2. 사이 크기로 정렬하기이것 또한 반례가 바로 나온다. 3. 끝점 기준으로 정렬하기이것은 반례가 안보인다. 한번 시도해볼 가치가 충분하다. 코드 구현#include #include #include#include#include using namespace std;typedef long lo.. 2024. 9. 15. [백준][스위핑] 2170 선 긋기 c++구현 목차https://www.acmicpc.net/problem/2170문제 문제 구현 아이디어두 점의 범위가 억이 넘어가므로 일단 공간 복잡도상으로 배열은 사용하지 못한다는 것을 알 수 있다.따라서 갱신을 하며 누적해주는 식으로 풀었다. 코드 구현#include #include #include#include#include typedef long long ll;using namespace std;vector>v;ll N, x, y;ll total = 0;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 0; i > x >> y; v.push_back({ .. 2024. 8. 24. [백준][이분탐색] 2632 피자판매 c++구현 목차https://www.acmicpc.net/problem/2632문제 문제 구현 방향연속된 값을 더하는 것이므로 일단 누적합이 생각났다.경우의 수가 매우 많으므로 각각의 경우를 구한뒤 합치는게 효율적이라고 생각했다. 문제 풀이 시 아이디어 1. 원형 배열 직선 배열로 만들기22172 아래와 같이 배열을 한번 더 합치면 원형 배열 구간합 탐색이 가능하다.2217222172 단 시작점이 초기 배열 사이즈-1 인덱스에 오면 탐색을 멈추어야 중복을 막을 수 있다.사이즈가 초기 배열 사이즈만큼일때는 한번 탐색하고 중단해야한다. 2. 각 경우 곱해서 구하기만들어 질 수 있는 각각의 경우를 구해 준 뒤 곱해서 더해준다. for (int i = 0; i 코드 구현#include #include #inclu.. 2024. 8. 19. [백준][구현] 15685 드래곤 커브 c++구현 목차https://www.acmicpc.net/problem/15685문제 문제 구현 방향각 드래곤의 방향을 구한뒤 맵과 벡터에 좌표를 넣고 탐색하는 식으로 구현했다. 문제 아이디어 1. 드래곤의 방향을 넣고 좌표 구하기드래곤의 움직임은 결국 방향벡터의 size만큼 세대별로 거꾸로 탐색해 방향벡터+1을 더한 값을 넣어주면 된다.void dragonMoving() { vector direct; for (int i = 0; i = 0; j--) { direct.push_back((direct[j] + 1) % 4); } } int sx = v[i].x; int sy = v[i].y; if.. 2024. 8. 17. 이전 1 2 3 4 5 ··· 25 다음 728x90
